64. 最小路径和（中等）

方法一：常规动态规划

1. 思路

   • 定义一个二维 dp 数组，其中 dp[i][j]表示从左上角开始到（i, j）位置的最优路径的数字和。
   • 因为每次都只能向下或者向右移动，所以很容易发现 dp数组第一行的元素一定只能从左边出发，所以第一行的元素初始化为 dp[0][i] = dp[0][i-1] + grid[0][i] ;
   • 第一列的元素一定只能从上边出发，所以第一列的元素初始化为 dp[j][0] = dp[j-1][0] + grid[j][0] ；
   • 其余元素，可能从上边出发，也可能从左边出发，因此我们需要比较得到二者中较小的那个值，作为最优路径，所以状态转移方程为 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; 。

2. 代码

   class Solution {
   public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));dp[0][0] = grid[0][0];// 对第一列初始化for(int i=1; i<m; ++i){dp[i][0] = dp[i-1][0] + grid[i][0];}// 对第一行初始化for(int j=1; j<n; ++j){dp[0][j] = dp[0][j-1] + grid[0][j];}for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];}}return dp[m-1][n-1];}
   };
   

3. 收获

   • 这道题蛮简单的，自己思考做出。

方法二：状态压缩

1. 思路

   • 因为 dp 矩阵的每一个值只和左边和上面的值相关，所以我们可以使用空间压缩将 dp 数组压缩为一维。对于第 i 行，在遍历到第 j 列的时候，第 j-1 列已经计算过了，所以 dp[j-1] 代表原先对应的 dp[i][j-1] 的值；而 dp[j] 待更新，当前存储的值是在 i-1 行的时候计算的，所以代表 dp[i-1][j] 的值。

2. 代码

   class Solution {
   public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<int> dp(n, 0);for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(i == 0 && j == 0){dp[j] = grid[i][j];}else if(i == 0){// 第一行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];}
   };
   

3. 收获

   • 很少接触空间压缩，看了思路不太理解，模拟一下就很好懂了。