## (Minimum Path Sum)

Given a $m \times 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.

Thoughts:
Because the grid is filled with non-negative numbers. Standing at any position ($i, j$), the minimum sum we can get is $\text{grid}[i,j] + \min$(minimum sum starting from$[i+1,j]$, minimum sum starting from $[i,j+1]$). Hence we find the recursive structure of this problem. The base case would be one element only, one row only and one column only. Notice that we could end up with repeating computations a lot (e.g., right->down and down->right), hence we should employ dynamic programming, in which we introduce a hashmap to cache the partial result.

Code (Java):

public class Solution {

private Map<List<Integer>, Integer> map =
new HashMap<List<Integer>, Integer>();

public int minPathSum(int[][] grid) {
map.clear();
return minPathSumRec(grid, 0, 0);
}

private int minPathSumRec(int[][] grid, int i, int j) {
List<Integer> pair = new ArrayList<Integer>();
if(map.get(pair) != null)
return map.get(pair);
else {
int r = grid[i][j];;
if(i == grid.length-1 && j == grid[0].length - 1)
r += 0;
else if(i == grid.length - 1)
r += minPathSumRec(grid, i, j + 1);
else if(j == grid[0].length - 1)
r += minPathSumRec(grid, i + 1, j);
else
r += Math.min(minPathSumRec(grid, i + 1, j),
minPathSumRec(grid, i, j + 1));
map.put(pair, r);
return r;
}
}
}


Code (C++):

class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
cache.clear();
return minPathSumRec(grid, 0, 0);
}

private:
map<vector<int>, int> cache;

int minPathSumRec(vector<vector<int> > &grid, int i, int j) {
vector<int> pair(2);
pair[0] = i;
pair[1] = j;
if(cache.find(pair) != cache.end())
return cache[pair];
else {
int r = grid[i][j];
if(i == grid.size() -1 && j == grid[0].size() - 1)
r += 0;
else if(i == grid.size() - 1)
r += minPathSumRec(grid, i, j + 1);
else if(j == grid[0].size() - 1)
r += minPathSumRec(grid, i + 1, j);
else
r += min(minPathSumRec(grid, i, j + 1),
minPathSumRec(grid, i + 1, j));
cache[pair] = r;
return r;
}
}
};


1. Nikhil Menon
Jun 19, 2014 @ 17:27:24

Hi Runhe,

Nice work with the blog.

If I could suggest an optimization, you could use an array of integers instead of the the has map of list of integers to integer. All we need to do is convert the indexes of the grid as if they belonged to a linear data structure.

In this case, it would be:

Total column count *i + j,

Where i => row index of cell
j => column index of cell.