买衣服网站排名,自助建站最大,网站建设教程pdf百度云,辽宁金帝建设集团网站本专栏内容为#xff1a;算法学习专栏#xff0c;分为优选算法专栏#xff0c;贪心算法专栏#xff0c;动态规划专栏以及递归#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习#xff0c;你可以了解并掌握算法。 #x1f493;博主csdn个人主页#xff1a;小… 本专栏内容为算法学习专栏分为优选算法专栏贪心算法专栏动态规划专栏以及递归搜索与回溯算法专栏四部分。 通过本专栏的深入学习你可以了解并掌握算法。 博主csdn个人主页小小unicorn ⏩专栏分类动态规划专栏 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 专题二 题目来源题目描述题目解析算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值 代码实现 题目来源
本题来源为 Leetcode 931. 下降路径最小和 题目描述
给你一个 n x n 的 方形 整数数组 matrix 请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列即位于正下方或者沿对角线向左或者向右的第一个元素。具体来说位置 (row, col) 的下一个元素应当是 (row 1, col - 1)、(row 1, col) 或者 (row 1, col 1) 。
题目解析
题目很好理解注意一点就是选择下一行发的元素是离他最近的三个位置的元素。
算法原理
1.状态表示
经验题目要求
对于本题而言就是
dp[i][j]表示走到[i,j]位置的时候最小的下降路径
2.状态转移方程
分三种情况
因此状态方程为
dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j1]))matrix[i-1][j-1];3.初始化
本次的初始化需要加两列一行。
4.填表顺序
整体从上往下
5.返回值
返回最后一行的最小值
代码实现
动态规划的代码基本就是固定的四步
1.创建dp表
2.初始化
3.填表
4.返回值本题完整代码实现
class Solution
{
public:int minFallingPathSum(vectorvectorint matrix) {int nmatrix.size();//创建dp表vectorvectorint dp(n1,vectorint(n2,INT_MAX));//初始化第一行for(int i0;in2;i)dp[0][i]0;//填表for(int i1;in;i){for(int j1;jn;j){//抄状态转移方程dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j1]))matrix[i-1][j-1];}}int retINT_MAX;for(int j1;jn;j){retmin(ret,dp[n][j]);}return ret;}
};时间复杂度O(N) 空间复杂度O(N)
