# Minimum Path Sum Problem statement

Given a `m x n` `grid` filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

If you notice this problem, from a position we can move right or down. Let’s go through my thought process. First, can I select the best path from a given position? The possible way is selecting greedily. But this will fail in the first example itself, we are picking 3 instead of 1 from 1st position.

So I know, greedy won’t work. Can I do an exhaustive search? Let’s check the complexity. For every position, there is 2 path. so O(2^N).

The complexity is high but that’s the only thing I know, let’s go for it.

``````public int recurse(int [][] grid, int i, int j)
{
// If reached the last element return the element
if(i == grid.length - 1 && j == grid.length - 1)
{
return grid[i][j];
}
int min = Integer.MAX_VALUE;
// if right is valid path visit
if(i + 1 < grid.length)
{
min = Math.min(min, recurse(grid, i + 1, j));
}
// if down is a valid path visit
if(j + 1 < grid.length)
{
min = Math.min(min, recurse(grid, i, j + 1));
}
return min + grid[i][j];
}``````

In the above code, I’m exploring all possible paths. If we create a recurse graph for this. It will look like this.

If you see, we are calculating the same node multiple times, if I already calculated for node(i,j), there is no need to calculating again. Let’s introduce a caching layer, which will save the answer for (i,j) if the we need it again, we can just return that value.

``````// Initialize with all one
int cache[][];
public int recurse(int [][] grid, int i, int j)
{
if(i == grid.length - 1 && j == grid.length - 1)
{
return grid[i][j];
}
// If once calculate just return it
if(cache[i][j] != -1)
{
return cache[i][j];
}
int min = Integer.MAX_VALUE;
if(i + 1 < grid.length)
{
min = Math.min(min, recurse(grid, i + 1, j));
}
if(j + 1 < grid.length)
{
min = Math.min(min, recurse(grid, i, j + 1));
}
cache[i][j] = min + grid[i][j];
return cache[i][j];
}``````

After caching the result the graph will look like this, where the colored nodes are calculated only once and returns the same result next time if asked.