公司建设网站的报告,吉首做网站,姜堰做网站,北太平庄网站建设1. 下降路径最小和 题目链接#xff1a; 931. 下降路径最小和 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/minimum-falling-path-sum/description/ 2. 算法原理 状态表示#xff1a;以莫一个位置位置为结尾 dp[i#xff0c;j]表示#xff1a;到…1. 下降路径最小和 题目链接 931. 下降路径最小和 - 力扣LeetCodehttps://leetcode.cn/problems/minimum-falling-path-sum/description/ 2. 算法原理 状态表示以莫一个位置位置为结尾 dp[ij]表示到达[ij]位置的时候此时的最小下降路径 2. 状态转移方程 根据最近的一步来划分问题 以最小的下降路径到达A位置然后再走一步到达目的地 到达dp[i][j]有三种情况 1. 从左上方位置过来[i-1j-1] - [ij]dp[i-1j-1] m[i][j] (缩写为x) 2. 从正上方位置过来[i-1j] - [ij]dp[i-1j] m[i][j] (缩写为y) 3. 从右上方位置过来[i-1j1] - [ij]dp[i-1j1] 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(vectorvectorint matrix) {//本题是方形所以不需要mint n matrix.size();//多加了一行两列初始化先把虚拟节点都初始化为正无穷大vectorvectorintdp(n 1, vectorint(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;}
}; 完结撒花~
