目录
题目
题目解析
思路
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开始走，那么第二行，只能走6，5或者4。每走一步加上该位置的值就行，根据规则走到最后 一行 就算结束，返回最小的那个就行。如果是边界，也就是只有两个位置离它最近。
思路
1.状态表示
状态表示，我们还是选用最常用的方法——选用以某一个位置为结尾，也就是从第一行走到该位置，题目要求，最小路径，所以状态表示可以看成dp[i][j]——从开始走到该【i，j】位置的最小的下降路径。
2.状态转移方程
根据最近的一步划分路径，最近的路径，到达【i，j】位置，可以从【i-1，j-1】位置，【i-1，j】或者【i-1，j+1】位置到达，所以应当分三种情况讨论。
a)从【i-1，j-1】位置到达【i，j】位置
要得到第一行到【i，j】位置的最小路径，就要得到第一行到【i-1，j-1】的最小路径，然后加上【i-1，j-1】位置上面的值就是，第一行到【i，j】位置的最小值。而第一行到【i-1，j-1】位置的最小路径可以用dp[i-1][j-1]表示，
所以此情况下的状态转移方程就是dp[i][j]=dp[i-1][j-1]+matrix[i-1][j-1]
b)从【i-1，j】位置到达【i，j】位置
同理，得到这个状态转移方程dp[i][j]=dp[i-1][j]+matrix[i-1][j]
c)从【i-1，j+1】位置到达【i，j】位置
同理，得到这个状态转移方程dp[i][j]=dp[i-1][j+1]+matrix[i-1][j+1]
然后取这三种情况的最小值。
3.初始化
初始化是为了让填表的时候不要越界。我们要算第一行到指定位置的路径最小值，也就是算dp[i][j]，根据状态转移方程可以看出要算dp[i][j]，要先得到dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1],第一行和第一列和最后一列，这三个位置是不全的，所以要初始化第一行和第一列，最后一列的位置。
之前学过，虚拟节点的方式，把需要的位置补起来，填上能使结果正确的值就行，补虚拟结点的方式，如下图所示。
现在要确定里面要填什么值，才能使结果正确，我们先来看不加虚拟结点的时候那里面应该填什么？
对于第一行，比如：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 (a<b)?a:b;
}
int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize)
{
int nummin=INT_MAX;
int n=matrixColSize[0];
//创建一个dp表
int dp[102][102]={INT_MAX};
//初始化
for(int i=0;i<102;i++)
for(int j=0;j<102;j++)
{
dp[i][j]=INT_MAX;
}
for(int j=0;j<n+2;j++)dp[0][j]=0;
//填表
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=min( min(dp[i-1][j],dp[i-1][j-1]) , dp[i-1][j+1] ) +matrix[i-1][j-1];
}
}
for(int j=1;j<=n;j++)
{
nummin=min(nummin,dp[n][j]);
}
return nummin;
}空间复杂度：O()文章来源：https://www.toymoban.com/news/detail-849552.html
时间复杂度：O()文章来源地址https://www.toymoban.com/news/detail-849552.html
到了这里，关于动态规划|【路径问题】|931.下降路径最小和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
