软件怎么做出来的,长春网站优化团队,国内公司网站需要备案,代理ip大全目录
题目
题目解析
思路
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
代码 题目
931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix #xff0c;请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开…目录
题目
题目解析
思路
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
代码 题目
931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix 请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列即位于正下方或者沿对角线向左或者向右的第一个元素。具体来说位置 (row, col) 的下一个元素应当是 (row 1, col - 1)、(row 1, col) 或者 (row 1, col 1) 。
示例 1 输入matrix [[2,1,3],[6,5,4],[7,8,9]]
输出13
解释如图所示为和最小的两条下降路径示例 2 输入matrix [[-19,57],[-40,-5]]
输出-59
解释如图所示为和最小的下降路径
提示
n matrix.length matrix[i].length1 n 100-100 matrix[i][j] 100
题目解析 题目是给一个n*n的矩阵矩阵里面有值从第一行到最后一行所走过的最小值从第一行元素的任意一个开始往最后一行走 既然是最小值那没每次就要挑下一行的最小值走而这个不是随便挑的是以第一行这个位置在第二行离的最近的三个位置中跳最小的值图示如下图。 如果第一行从1开始走那么第二行只能走65或者4。每走一步加上该位置的值就行根据规则走到最后 一行 就算结束返回最小的那个就行。如果是边界也就是只有两个位置离它最近。
思路
1.状态表示 状态表示我们还是选用最常用的方法——选用以某一个位置为结尾也就是从第一行走到该位置题目要求最小路径所以状态表示可以看成dp[i][j]——从开始走到该【ij】位置的最小的下降路径。
2.状态转移方程 根据最近的一步划分路径最近的路径到达【ij】位置可以从【i-1j-1】位置【i-1j】或者【i-1j1】位置到达所以应当分三种情况讨论。
a)从【i-1j-1】位置到达【ij】位置 要得到第一行到【ij】位置的最小路径就要得到第一行到【i-1j-1】的最小路径然后加上【i-1j-1】位置上面的值就是第一行到【ij】位置的最小值。而第一行到【i-1j-1】位置的最小路径可以用dp[i-1][j-1]表示 所以此情况下的状态转移方程就是dp[i][j]dp[i-1][j-1]matrix[i-1][j-1]
b)从【i-1j】位置到达【ij】位置 同理得到这个状态转移方程dp[i][j]dp[i-1][j]matrix[i-1][j]
c)从【i-1j1】位置到达【ij】位置 同理得到这个状态转移方程dp[i][j]dp[i-1][j1]matrix[i-1][j1]
然后取这三种情况的最小值。
3.初始化 初始化是为了让填表的时候不要越界。我们要算第一行到指定位置的路径最小值也就是算dp[i][j]根据状态转移方程可以看出要算dp[i][j]要先得到dp[i-1][j],dp[i-1][j-1],dp[i-1][j1],第一行和第一列和最后一列这三个位置是不全的所以要初始化第一行和第一列最后一列的位置。 之前学过虚拟节点的方式把需要的位置补起来填上能使结果正确的值就行补虚拟结点的方式如下图所示。 现在要确定里面要填什么值才能使结果正确我们先来看不加虚拟结点的时候那里面应该填什么 对于第一行比如dp[0][0]dp[0][0]表示从第一行到当前位置的最小值可以看出当前位置就是在第一行也就是自己到自己也就等于本身矩阵里面的值这样 我们将加的第一行虚拟结点赋值为0就可以不影响结果。 对于第一列和最后一列对于第一列从第二行开始它们只是缺了左上角那个数其他两个都在如果不加虚拟结点也就是说只在这两个结点里面挑一个最小的加上就行也就是说 虚拟结点里面的值不能影响dp[i][j]的结果 虚拟结点里面的值要比其他两个值都大为了确保起见应该将虚拟结点赋值为正的无穷大。 我们加完之后还要解决下标映射的问题加了一行所以就 整体向下挪了一行左边增加一列也就是向右挪了一列。 所以当我们算dp[1][1]的值我们要用martix[0][0]值来计算。
4.填表顺序
填表顺序还是从上到下从左到右
5.返回值
因为是要到达最后一行并且是要最小值所以我们返回dp表中最后一行的最小值就行
代码 初始化技巧我们为了方便初始化如果我们在定义dp表时将所有值定义为0后面初始化的时候要改两列的值所以这里可以我们一开始就将每个初始化正的无穷大。
int min(int a,int b)
{return (ab)?a:b;
}
int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize)
{int numminINT_MAX;int nmatrixColSize[0];//创建一个dp表int dp[102][102]{INT_MAX};//初始化for(int i0;i102;i)for(int j0;j102;j){dp[i][j]INT_MAX;}for(int j0;jn2;j)dp[0][j]0;//填表 for(int i1;in;i){for(int j1;jn;j){dp[i][j]min( min(dp[i-1][j],dp[i-1][j-1]) , dp[i-1][j1] ) matrix[i-1][j-1];}}for(int j1;jn;j){numminmin(nummin,dp[n][j]);}return nummin;
}
空间复杂度O()
时间复杂度O()
