【从0到1冲刺蓝桥杯国赛】每日一练——最小路径和

最小路径和https://leetcode-cn.com/problems/minimum-path-sum/

题目描述：

思路分析：

典型得动态规划简单题，如果再开辟一个dp二维数组也可以，但其实是浪费空间，直接在原数组上修改值就可以，或者滚动数组也行，总之dp二维数组大家都能想到也不是什么最优解

原数组C++实现： 

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

 滚动数组C++实现：

class Solution{public:int minPathSum(vector<vector >& grid){//首先获取二维动态数组grid的长度int m = grid.size(); //获取行数m int n = grid[0].size(); //获取列数n //使用滚动数组dp //我们直接把dp初始化成grid第一行,大小为n vector dp(grid[0]); //初始化dp数组for(int i = 1; i < n; i++)dp[i] = dp[i] + dp[i - 1]; //维护dp数组for(int i = 1; i < m; i++){dp[0] = dp[0] + grid[i][0];for(int j = 1; j < n; j++){dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];}} return dp[n - 1];}};

ChinaFonts