动态规划是求解“最小路径”的常用方法之一，LeetCode上关于“最小路径”的题目如下：
- 64.最小路径和：https://leetcode-cn.com/problems/minimum-path-sum/
- 120.三角形最小路径和：https://leetcode-cn.com/problems/triangle/
- 931.下降路径最小和：https://leetcode-cn.com/problems/minimum-falling-path-sum/
- 1289.下降路径最小和Ⅱ：https://leetcode-cn.com/problems/minimum-falling-path-sum-ii/
本文，Jungle将采用动态规划，一举解决上述问题。
关于动态规划，可以访问Jungle之前的博客：
- [LeetCode]动态规划及LeetCode题解分析
- 动态规划LeetCode[简单]题全解
- [LeetCode]动态规划之打家劫舍ⅠⅡⅢ
- [LeetCode]动态规划，一举歼灭“股票买卖的最佳时机”问题
1
思路分析
我们以64.最小路径和为例，分析采用动态规划求解该类问题的基本思路。题目描述如下：
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
在之前的文章我们已经提到过，使用动态规划求解问题的三大步骤，这里我们也将遵循这三大步骤：
（1）明确数组元素代表的含义
题目中是给定二维地图，我们使用二维数组dp[][]。那么对于数组元素dp[i][j]代表什么呢？——机器人走到网格(i,j)时的最小路径值。
（2）寻找递推关系，务必考虑特殊情况下的递推关系
题目中明确告诉“机器人每次只能向下或者向右移动一步”，因此，机器人走到(i,j)，有可能是从(i-1,j)向下走，也可能是从(i,j-1)向右走一步。到底该走哪一步呢？因为要求路径和最小，所以取决于dp[i-1][j]和dp[i][j-1]的大小。也就是说，dp[i][j]=grid[i][j] min(dp[i-1][j] dp[i][j-1]).
这里有没有特殊情况呢？显然有的，那就是机器人位于网格边界时（网格上面第一横排和左边第一竖排），上述递推关系需要修改：
- 当机器人位于网格第一横排时，i=0，dp[0][j]只能从dp[0][j-1]向右移动一步得到，即dp[0][j] = grid[0][j] dp[0][j-1]；
- 当机器人位于网格第一竖排时，j=0，dp[i][0]只能从dp[i-1][0]向下移动一步得到，即dp[i][0] =grid[i-1][0] dp[i-1][0]；
（3）数组初始化
机器人最初位于网格左上角，dp[0][0]是唯一开始点，所以dp[0][0] = grid[0][0].
（4）代码
本题不必重新声明二维数组dp，可以直接利用原有二维数组。
代码语言：javascript复制int minPathSum(vector<vector<int>>& grid) {
int i = 0, j = 0;
for (i = 0; i<grid.size(); i ){
for (j = 0; j<grid[0].size(); j ){
if (i == 0 && j == 0){
continue;
}
else if (i == 0){
grid[i][j] = grid[i][j - 1];
}
else if (j == 0){
grid[i][j] = grid[i - 1][j];
}
else{
grid[i][j] = grid[i][j] (grid[i][j - 1]<grid[i - 1][j] ? grid[i][j - 1] : grid[i - 1][j]);
}
}
}
return grid[grid.size() - 1][grid[0].size() - 1];
}2
LeetCode题解
64. 最小路径和
见上述题解分析
120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 3 5 1 = 11）。
这题把矩形换成了三角形。有什么区别？总体上思路是一样的，区别在于边界条件。
（1）明确数组元素代表的含义
dp[i][j]——走到网格(i,j)时的最小路径值。
（2）寻找递推关系，务必考虑特殊情况下的递推关系
题目中要求“每一步只能移动到下一行中相邻的结点上”，因此，走到(i,j)，有可能是从(i-1,j-1)向下走，也可能是从(i-1,j)向下走。到底该走哪一步呢？因为要求路径和最小，所以取决于dp[i-1][j]和dp[i][j-1]的大小。也就是说，dp[i][j]=triangle[i][j] min(dp[i-1][j] dp[i-1][j]).
这里同样有特殊情况——位于网格边界时。比上一题更加复杂的是，这道题有三角形顶点和三角形两腰上三个边界条件需要考虑，上述递推关系需要修改：
- 当位于三角形左腰上时，即j=0，dp[i][0]只能从dp[i-1][0]向下移动一步得到，即dp[i][j] = triangle[i][j] dp[i - 1][j]；
- 当位于三角形右腰上时，即i=j，dp[i][j]只能从dp[i-1][j-1]向下移动一步得到，即dp[i][j] = triangle[i][j] dp[i - 1][j - 1]；
同时，因为这一题目是要求走到底部，而不是固定走到最右下角的位置。所以定义变量min保存最小值。
（3）数组初始化
最初位于三角形顶点，dp[0][0]是唯一开始点，所以dp[0][0] = triangle[0][0].
（4）代码
代码语言：javascript复制int minimumTotal(vector<vector<int>>& triangle) {
int col = triangle.size();
if (col == 0){
return 0;
}
if (col == 1){
return triangle[0][0];
}
int **dp = new int*[col];
for (int i = 0; i<col; i ){
dp[i] = new int[i 1];
}
dp[0][0] = triangle[0][0];
int min = 0;
for (int i = 1; i<col; i ){
for (int j = 0; j<triangle[i].size(); j ){
if (j == 0){
dp[i][j] = triangle[i][j] dp[i - 1][j];
min = dp[i][j];
}
else if (j == i){
dp[i][j] = triangle[i][j] dp[i - 1][j - 1];
}
else{
dp[i][j] = triangle[i][j] (dp[i - 1][j - 1] < dp[i - 1][j] ? dp[i - 1][j - 1] : dp[i - 1][j]);
}
if (dp[i][j]<min){
min = dp[i][j];
}
}
}
return min;
}931. 下降路径最小和
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例： 输入：[[1,2,3],[4,5,6],[7,8,9]] 输出：12 解释： 可能的下降路径有： [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9] [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9] [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9] 和最小的下降路径是 [1,4,7]，所以答案是 12。 提示： 1 <= A.length == A[0].length <= 100 -100 <= A[i][j] <= 100
（1）明确数组元素代表的含义
dp[i][j]——走到网格(i,j)时的最小路径和。
（2）寻找递推关系，务必考虑特殊情况下的递推关系
题目中要求“从每一行中选择一个元素”并且“在下一行选择的元素和当前行所选元素最多相隔一列”，因此，走到(i,j)，可能是从(i-1,j-1)、(i-1,j)或者(i-1,j 1)三个位置出发达到。到底该走哪一步呢？因为要求路径和最小，所以取决于dp[i-1][j-1]、dp[i-1][j]和dp[i-1][j 1]的大小，即：
dp[i][j] = A[i][j] min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j 1])).
特殊情况——位于网格边界时：
- 当位于左边界时，即j=0，dp[i][0]只能从dp[i-1][j]或dp[i-1][j 1]出发达到，即dp[i][j] = A[i][j] min(dp[i-1][j],dp[i-1][j 1])；
- 当位于右边界时，即j=len-1，dp[i][j]只能从dp[i-1][j-1]或dp[i-1][j]出发达到，即dp[i][j] = A[i][j] min(dp[i-1][j-1],dp[i-1][j])；
同时，因为这一题目是要求走到底部，而不是固定走到最右下角的位置。所以定义变量Min保存最小值。
（3）数组初始化
题目要求，“下降路径可以从第一行中的任何元素开始”，所以dp[0][j] = A[0][j]
（4）代码
代码语言：javascript复制int minFallingPathSum(vector<vector<int>>& A) {
int row = A.size();
int col = A[0].size();
if (row == 0 || col == 0){
return 0;
}
if (row == 1){
sort(A[0].begin(), A[0].end());
return A[0][0];
}
vector<vector<int>>dp(row, vector<int>(col, 0));
int Min = 0;
for (int j = 0; j<col; j ){
dp[0][j] = A[0][j];
}
for (int i = 1; i<row; i ){
for (int j = 0; j<col; j ){
if (j == 0){
dp[i][j] = A[i][j] min(dp[i - 1][j], dp[i - 1][j 1]);
}
else if (j == col - 1){
dp[i][j] = A[i][j] min(dp[i - 1][j - 1], dp[i - 1][j]);
}
else{
dp[i][j] = A[i][j] min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j 1]));
}
if (i == row - 1){
if (j == 0){
Min = dp[i][0];
}
if (dp[i][j]<Min){
Min = dp[i][j];
}
}
}
}
return Min;
}1289. 下降路径最小和 II
一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。请你返回非零偏移下降路径数字和的最小值。
示例 1： 输入：arr = [[1,2,3],[4,5,6],[7,8,9]] 输出：13 解释： 所有非零偏移下降路径包括： [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] 下降路径中数字和最小的是 [1,5,7] ，故答案是 13 。 提示： 1 <= arr.length == arr[i].length <= 200 -99 <= arr[i][j] <= 99
这一题与上一题的区别在于，“按顺序选出来的数字中，相邻数字不在原数组的同一列”。这道题标记为“困难”，难吗？不难。
（1）明确数组元素代表的含义
dp[i][j]——走到网格(i,j)时的最小路径和。
（2）寻找递推关系，务必考虑特殊情况下的递推关系
题目中要求“从每一行中选择一个元素”并且“相邻数字不在原数组的同一列”，因此，走到(i,j)，是由除了(i-1,j)之外的其他网格出发达到。要求路径最小，因此需要找到在(i,j)上一步的最小路径值。所以，dp[i][j] = arr[i][j] min_dp(dp,i-1,j)，其中min_dp是一个函数，返回第i-1行中的最小路径值，第三个参数代表当前的j，所以在查找第i-1行中的最小路径值时，要排除掉第j个位置的路径值。
同时，因为这一题目是要求走到底部，而不是固定走到最右下角的位置。所以定义变量res保存最小值。
（3）数组初始化
题目要求，“下降路径可以从第一行中的任何元素开始”，所以dp[0][j] = arr[0][j]
（4）代码
代码语言：javascript复制int min_dp(vector<vector<int>>& dp, int i, int not_j){
int Min = 201;
for (int jj = 0; jj<dp.size(); jj ){
if (jj == not_j){
continue;
}
if (dp[i][jj]<Min){
Min = dp[i][jj];
}
}
return Min;
}
int minFallingPathSum(vector<vector<int>>& arr) {
int len = arr.size();
if (len == 0){
return 0;
}
if (len == 1){
return arr[0][0];
}
vector<vector<int>>dp(len, vector<int>(len, 0));
int res;
for (int k = 0; k<len; k ){
dp[0][k] = arr[0][k];
}
for (int i = 1; i<len; i ){
for (int j = 0; j<len; j ){
dp[i][j] = arr[i][j] min_dp(dp, i - 1, j);
if (i == len - 1){
if (j == 0){
res = dp[i][j];
}
else if (dp[i][j]<res){
res = dp[i][j];
}
}
}
}
return res;
}
