动态规划 —— 路径问题-下降路径最小和

1. 下降路径最小和

题目链接：

931. 下降路径最小和 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-falling-path-sum/description/

 

 

---

2.  算法原理 

状态表示：以莫一个位置位置为结尾

   

dp[i，j]表示：到达[i，j]位置的时候，此时的最小下降路径

2. 状态转移方程

  

根据最近的一步来划分问题：

      

                                以最小的下降路径到达A位置，然后再走一步到达目的地 

到达dp[i][j]有三种情况：

                               1. 从左上方位置过来：[i-1，j-1] -> [i，j]，dp[i-1，j-1] + m[i][j]

                                                                                                 (缩写为x)     

     

                               2. 从正上方位置过来：[i-1，j] -> [i，j]，dp[i-1，j] + m[i][j]

                                                                                                 (缩写为y)

     

                               3. 从右上方位置过来：[i-1，j+1] -> [i，j]，dp[i-1，j+1] + m[i][j]

                                                                                                    (缩写为z)

     

本题的状态转移方程是：dp[i][j] = min(x,y,z)+m[i][j]

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

   

我们可以在上面的一行和左边还有右边的一列再额外的加上一行和两列的虚拟节点

    

原始矩阵里第一行的值是不能被改变的，不然会影响到最终结果，所以第一行的虚拟节点应该全部初始化为0，而左右两列不能初始化为0，因为为0的话就可能会参与最小值的计算，会影响到最终结果，所以应该初始化为正无穷大

    

本题的下标映射关系：因为本题给了一个矩阵，而我们又额外的加上一行和两列的虚拟节点，所以我们的下标都统一往右下角移动了一位，如果想找回之前对应的位置，那么下标需要进行统一减1（横纵坐标）

4. 填表顺序 

    

本题的填表顺序是：从上往下填写每一行，每一行的值是从左往右

5. 返回值 ：题目要求 + 状态表示    

    

本题的返回值是：最后一行里面的最小值

---

3.代码 

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值 

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {//本题是方形，所以不需要mint  n = matrix.size();//多加了一行两列，初始化先把虚拟节点都初始化为正无穷大vector<vector<int>>dp(n + 1, vector<int>(n + 2, INT_MAX));//将虚拟节点的第一行初始化为0for (int j = 0; j < n + 2; j++) dp[0][j] = 0;//额外的加上一行和两列的虚拟节点，所以从1开始for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)//这里的matrix[i-1][j-1]也是加上一行和一列的虚拟节点，所以要横纵-1dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))+ matrix[i - 1][j - 1];//返回最后一行里面的最小值//定义一个临时变量ret，不能将ret的的值定义为0，不然会影响到最终结果int ret = INT_MAX;for (int j = 1; j <= n; j++)ret = min(ret, dp[n][j]);//找到最后一行的最小和return ret;}
};

---

完结撒花~