[LeetCode] Minimum Path Sum 解题报告

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:    }  

注意，Line 6，初始值是INT_MAX。因为Line 13里面用了min函数。