算法 动态规划 【LeetCode】64. 最小路径和

64. 最小路径和（中等）

方法一：常规动态规划

思路

定义一个二维 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]; 。 代码 class Solution {

public:

int minPathSum(vector>& grid) {

int m = grid.size(), n = grid[0].size();

vector> dp(m, vector(n, 0));

dp[0][0] = grid[0][0];

// 对第一列初始化

for(int i=1; i

dp[i][0] = dp[i-1][0] + grid[i][0];

}

// 对第一行初始化

for(int j=1; j

dp[0][j] = dp[0][j-1] + grid[0][j];

}

for(int i=1; i

for(int j=1; j

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

}

}

return dp[m-1][n-1];

}

};

收获

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

方法二：状态压缩

思路

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

public:

int minPathSum(vector>& grid) {

int m = grid.size(), n = grid[0].size();

vector dp(n, 0);

for(int i=0; i

for(int j=0; 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];

}

};

收获

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

好文阅读

 您阅读本篇文章共花了：