首页 > 代码库 > [LeetCode]Minimum Path Sum
[LeetCode]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.
解答：本题采用动态规划的方法，逐列扫描直至目标点
先计算第一行的路径权值f(0),f(1),f(2)，接着进行换行，再逐列比较选择路径，依次类推，最终到达目标点。
代码如下：
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==1&&n==1) 7 return grid[0][0]; 8 int minsum=grid[0][0]; 9 vector<int> f;10 f.resize(n);11 f[0]=grid[0][0];12 //设置一个迭代结构13 for(int i=1;i<n;i++){14 f[i]=grid[0][i]+f[i-1];15 }16 for(int i=1;i<m;i++){17 f[0]+=grid[i][0];18 for(int j=1;j<n;j++){19 f[j]=min(f[j-1],f[j])+grid[i][j];20 }21 }22 23 return f[n-1];24 }25 };
[LeetCode]Minimum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。