首页 > 其他 > 详细

Minimum Path Sum

时间:2014-10-06 19:58:10      阅读:262      评论:0      收藏:0      [点我收藏+]

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[i][j]表示走到(i,j)格子时,取得的最小数字,那么有

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

当i=0时,只能从左边过来,当j=0时,只能从上面过来

 1 class Solution {
 2 public:
 3     int minPathSum(vector<vector<int> > &grid) {
 4         int m = grid.size();
 5         int n = grid[0].size();
 6         if( m<0 || n<0 ) return 0;
 7         vector< vector<int> > dp(grid);
 8         for(int i=1; i<n; ++i) dp[0][i] += dp[0][i-1];
 9         for(int i=1; i<m; ++i) dp[i][0] += dp[i-1][0];
10         for(int i=1; i<m; ++i)
11             for(int j=1; j<n; ++j)
12                 dp[i][j] += min(dp[i-1][j], dp[i][j-1]);
13         return dp[m-1][n-1];
14     }
15 };

 

Minimum Path Sum

原文:http://www.cnblogs.com/bugfly/p/4008593.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!