首页 > 代码库 > 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[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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。