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.
解法一：
recursion的思路，不过通过不了OJ的runtime test。因为很多grid的node走了太多次了。。。
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int res = 0; if(grid.empty() || grid[0].empty()) return res; res += grid[0][0]; if(grid.size()==1){ for(int i=1; i<grid[0].size(); i++) res += grid[0][i]; return res; } if(grid[0].size()==1){ for(int i=1; i<grid.size(); i++) res += grid[i][0]; return res; } vector<vector<int>> down_grid, right_grid; for(int i=1; i<grid.size(); i++){ down_grid.push_back(grid[i]); } for(int i=0; i<grid.size(); i++){ vector<int> tmp = grid[i]; tmp.erase(tmp.begin()); right_grid.push_back(tmp); } int sum_down = minPathSum(down_grid); int sum_right = minPathSum(right_grid); res += min(sum_down, sum_right); return res; } }; 解法二：
还可以用dp的方法去做，复杂度显然就是O(m*n)了。用一个二维数组dp，dp[i][j]表示走到i,j时最小的sum，很容易得出递推公式是dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。
class Solution { public: int minPathSum(vector<vector<int>>& grid) { if(grid.empty() || grid[0].empty()) return 0; int m = grid.size(), n= grid[0].size(); int dp[m][n]; dp[0][0] = grid[0][0]; for(int i=1;i<m; i++) dp[i][0]=grid[i][0]+dp[i-1][0]; for(int j=1;j<n; j++) dp[0][j]=grid[0][j]+dp[0][j-1]; for(int i=1; i<m; i++) for(int j=1; j<n; j++){ dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]); } return dp[m-1][n-1]; } };
