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.
对m * n 的网格，求其左上角到右下角的最短路径和：
DP问题，计算式是：min(ret[i][j]) = min(ret[i - 1][j], ret[i][j - 1]) + input[i][j];
代码如下：
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == || grid[].size() == ) return ;
int szHor = grid.size();
int szVer = grid[].size();
vector<vector<int>> ret = grid;
ret[][] = grid[][]
for(int i = ; i < szHor; ++i){
ret[i][] = ret[i - ][] + grid[i][];
}
for(int i = ; i < szVer; ++i){
ret[][i] = ret[][i - ] + grid[][i];
}
for(int i = ; i < grid.size(); ++i){
for(int j = ; j < grid[].size(); ++j){
ret[i][j] = min(ret[i - ][j], ret[i][j - ]) + grid[i][j];
}
}
return ret[szHor - ][szVer - ];
}
};简单的DP问题，java版本代码如下所示：
public class Solution {
public int minPathSum(int[][] grid) {
if(grid.length == 0 || grid[0].length == 0)
return 0;
int szRol = grid.length;
int szCol = grid[0].length;
int [][] ret = new int [szRol][szCol];
ret[0][0] = grid[0][0];
for(int i = 1; i < szRol; ++i){
ret[i][0] = ret[i-1][0] + grid[i][0];
}
for(int i = 1; i < szCol; ++i){
ret[0][i] = ret[0][i-1] + grid[0][i];
}
for(int i = 1; i < szRol; ++i){
for(int j = 1; j < szCol; ++j){
ret[i][j] = Math.min(ret[i-1][j], ret[i][j-1]) + grid[i][j];
}
}
return ret[szRol-1][szCol-1];
}
}