LeetCode刷题（C++）——Minimum Path Sum（Medium）

分手后的思念是犯贱 2022-06-16 06:29 171阅读 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.

**思路：**利用动态规划。对于任意一点（i,j）,最小路径和存储在同样大小的矩阵dp中，假设到达点（i,j）的最小路径和为dp\[i\]\[j\]

（1）当（i，j）=（0,0）时，dp\[i\]\[j\]=grid\[0\]\[0\]

（2）当（i，j）位于第一行且 j>0时，dp\[i\]\[j\]=dp\[i\]\[j-1\]+grid\[i\]\[j\]，且只有这一种情况

（3）同理，当（i，j）位于第一列且i>0时，dp\[i\]\[j\]=dp\[i-1\]\[j\]+grid\[i\]\[j\]，且只有这一种情况

（4）除以上情况之外，对于任何（i，j），都有两种情况：一种是从（i-1，j）->（i，j）；一种是从（i，j-1）->（i，j）此时我们需要选择两种情况中路径和最小的一个，即 dp\[i\]\[j\] = min(dp\[i-1\[j\]，dp\[i\]\[j-1\])+grid\[i\]\[j\]

grid

代码实现如下：

class Solution {
 public:
 int minPathSum(vector<vector<int>>& grid) {
 if(grid.empty())
 return 0;
 int m=grid.size(),n=grid[0].size();
 vector<vector<int>> dp(m,vector<int>(n));
 for(int i=0; i<m;i++){
 for(int j=0; j<n;j++){
 if(i==0){
 if(j==0){
 dp[i][j]=grid[i][j];
 }
 else{
 dp[i][j] = dp[i][j-1]+grid[i][j]; }
 }
 else if(j==0){
 dp[i][j]=dp[i-1][j]+grid[i][j];
 }
 else{
 dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
 }
 }
 }
 return dp[m-1][n-1];
 }
 };

还可以对上面的空间进行优化，我们只需要用以为数组dp即可，代码如下：

class Solution {
 public:
 int minPathSum(vector<vector<int>>& grid) {
 if(grid.empty())
 return 0;
 int m=grid.size(),n=grid[0].size();
 vector<int> dp(n);
 for(int i=0; i<m;i++){
 for(int j=0; j<n;j++){
 if(i==0){
 if(j==0){
 dp[j]=grid[i][j];
 }
 else{
 dp[j] = dp[j-1]+grid[i][j]; 
 }
 }
 else if(j==0){
 dp[j]=dp[j]+grid[i][j];
 }
 else{
 dp[j]=min(dp[j],dp[j-1])+grid[i][j];
 }
 }
 }
 return dp[n-1];
 }
 };