Posted on 2014-01-19 02:57
Uriel 阅读(139)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
给一个数字矩阵，求从左上角到右下角数字和最小的一条路径，输出数字和，(每次仅能往右或往下走)
1 class Solution {
2 public:
3 int dp[1010][1010];
4 int minPathSum(vector<vector<int> > &grid) {
5 if(grid.empty()) return 0;
6 for(int i = 0; i < grid.size(); ++i) {
7 for(int j = 0; j < grid[0].size(); ++j) {
8 if(!i && !j) dp[i][j] = grid[i][j];
9 else if(!i) dp[i][j] = dp[i][j - 1] + grid[i][j];
10 else if(!j) dp[i][j] = dp[i - 1][j] + grid[i][j];
11 else
12 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
13 }
14 }
15 return dp[grid.size() - 1][grid[0].size() - 1];
16 }
17 };