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.
» Solve this problem[解题报告]
二维DP。设数组A[row][col],
Min[i][j] = min(Min[i-1][j], Min[i][j-1]) +A[i][j];
注意初始条件即可。
[Code]
1: int minPathSum(vector<vector<int> > &grid) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: if(grid.size() ==0) return 0;
5: int row = grid.size();
6: int col = grid[0].size();
7: int Min[row][col];
8: Min[0][0] =grid[0][0];
9: for(int i =1; i < row; i ++)
10: {
11: Min[i][0] =Min[i-1][0] + grid[i][0];
12: }
13: for(int i =1; i< col; i++)
14: {
15: Min[0][i] = Min[0][i-1] + grid[0][i];
16: }
17: for(int i =1; i< row; i++)
18: {
19: for(int j =1; j< col; j++)
20: {
21: Min[i][j] = min(Min[i-1][j], Min[i][j-1]) + grid[i][j];
22: }
23: }
24: return Min[row-1][col-1];
25: }
Update: 3/16/2013. Refactor code
没必要用二维数组，用滚动数组即可。
1: int minPathSum(vector<vector<int> > &grid) {
2: int row = grid.size();
3: if(row == 0) return 0;
4: int col = grid[0].size();
5: if(col == 0) return 0;
6: vector<int> steps(col, INT_MAX);
7: steps[0] =0;
8: for(int i =0; i< row; i++)
9: {
10: steps[0] = steps[0] + grid[i][0];
11: for(int j=1; j<col; j++)
12: {
13: steps[j]=min(steps[j], steps[j-1]) + grid[i][j];
14: }
15: }
16: return steps[col-1];
17: }