江苏工程建设信息官方网站,南昌城市旅游网站建设,怎么制作游戏app,wordpress 改语言设置1. 题目链接#xff1a;931. 下降路径最小和
2. 题目描述#xff1a; 给你一个 n x n 的 方形 整数数组 matrix #xff0c;请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始#xff0c;并从每一行中选择一个元素。在下一行选择…1. 题目链接931. 下降路径最小和
2. 题目描述 给你一个 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 3. 解法动态规划
3.1算法思路
3.1.1 状态表示
dp[i][j]表示到达[i,j]位置时所有下降路径中的最小和
3.1.2 状态转移方程
到达 [i,j]位置可能有三种情况 我们要的是三种情况下的最小值然后加上矩阵在[i,j]位置
于是dp[i,j]min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j1]))matrix[i,j]
3.1.3 初始化
可以在最前面加上一个辅助结点进行初始化。使用这种技巧需要注意两点 辅助结点里面的值要保证后续填表是正确的 下标的映射关系 在本题中需要加上一行并且加上两列。所有位置都初始化为无穷大然后将第一行初始化为0即可 3.1.4 填表顺序
从上往下
3.1.5 返回值
注意这里不是返回dp[m][n]的值
题目要求【只要到达最后一行】因此这里应该返回【dp表最后一行的最小值】
3.2 C算法代码
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {int nmatrix.size();//创建dp表vectorvectorintdp(n1,vectorint(n2,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(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j1]))matrix[i-1][j-1];}}int retINT_MAX;for(int j0;jn;j){retmin(ret,dp[n][j]);}//返回结果return ret; }
};
