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.
Subscribe to see which companies asked this question
分析：
很显然的动态规划问题。
令从（1，1）到（m,n）的最小和为result[m,n]
任何一个点都是来自上面的最小和或者来自右边的最小和与当前位置的值相加的加过
显然result[m,n]=min(result[m-1,n]+grid[m,n],result[m,n-1]+grid[m,n])
注意初始化问题
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int row=grid.size();//行
int col=grid[0].size();
vector< vector<int> > result(row);
for(int i=0;i <row ;i++)
result[i].resize(col,0);//设置数组的大小row行，col列
result[0][0]=grid[0][0];//初始化
for(int i=1;i<col;i++)//初始化第一行
result[0][i]=result[0][i-1]+grid[0][i];
for(int i=1;i<row;i++)//初始化第一列
result[i][0]=result[i-1][0]+grid[i][0];
for(int i=1;i<row;i++)//计算中间结果
for(int j=1;j<col;j++)
result[i][j]=min(result[i][j-1]+grid[i][j],result[i-1][j]+grid[i][j]);
return result[row-1][col-1];
}
};
注：本博文为EbowTang原创，后续可能继续更新本文。如果转载，请务必复制本条信息！
原文地址：http://blog.csdn.net/ebowtang/article/details/50640213
原作者博客：http://blog.csdn.net/ebowtang
<LeetCode OJ> 64. Minimum Path Sum
原文：http://blog.csdn.net/ebowtang/article/details/50640213