[LeetCode] Minimum Path Sum
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.
解题思路：
这道题找到从左上角到右下角最小路径长度。每个方格有一个值，路径只能往右走或者往下走。
用DP算法。
d[i][j]表示从0,0到i,j的最短路径长度。那么有递推公式：
d[i][j] = grid[i][j]+min(d[i-1][j], d[i][j-1])。
还得注意边界条件。
下面是程序代码：
class Solution {
public:
int minPathSum(vector>& grid) {
int m = grid.size();
if(m<=0){
return 0;
}
int n = grid[0].size();
if(n<=0){
return 0;
}
vector> d(m, vector(n, 0));
for(int i=0; i0 && j>0){
d[i][j] += min(d[i-1][j], d[i][j-1]);
}else if(i>0){
d[i][j] += d[i-1][j];
}else if(j>0){
d[i][j] += d[i][j-1];
}
}
}
return d[m-1][n-1];
}
};
转载请注明： » [LeetCode] Minimum Path Sum
<!--
-->
原文作者：；如有侵权，请联系管理员删除。
上一篇：
2015年04月02日阿里笔试总结
下一篇：
PHP rand() 函数应该注意的问题
请登录后发表评论
登录
全部评论
