网站备案必须是企业吗,中国建设劳动学会监制网站,网页网站设计价格,wordpress seo联接插件#x1f388;算法那些事专栏说明#xff1a;这是一个记录刷题日常的专栏#xff0c;每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目#xff0c;在这立下Flag#x1f6a9; #x1f3e0;个人主页#xff1a;Jammingpro #x1f4d5;专栏链接… 算法那些事专栏说明这是一个记录刷题日常的专栏每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目在这立下Flag 个人主页Jammingpro 专栏链接算法那些事 每日学习一点点技术累计看得见 题目
题目描述
给你一个 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].length 1 n 100 -100 matrix[i][j] 100
题解
题目中说到在下一行选择的元素和当前行所选元素最多相隔一列即位于正下方或者沿对角线向左或者向右的第一个元素。这句话说的是第i行第j列的元素可以到达第i1行第j-1列、第i1行第j列、第i1行第j1列元素。如下图左图所示第0行第1列元素可以到达第1行第0列、第1行第1列、第1行第2列元素。也就是说当前元素向下走时可以向左下走、向下走或者向右下走。反过来说到达第i行第j列的上一步可以是第i-1第j-1列、第i-1行第j列、第i-1行第j1列如下图右图所示。 题目中所说的最小路径是指从第0行的任意一个元素出发每一步向左下、向下或向右下走1步一直到达最后一行将上述每一步到达的元素相加后得最小和。我们可以使用一个dp表二维数组保存到达第i行第j列的最小路径和。因为第0行是出发点所以dp[0][i]matrix[0][i]。如下图所示下图显示的内容为示例1↓↓↓ 余下第i行第0列的元素只能从上面一个元素或者从右上元素到达因为左上元素不存在故dp[i][0]min(dp[i-1][j],dp[i-1][j1])matrix[i][0]。以示例1为例计算第1行第0列元素示意图如下↓↓↓ 与下第i行最后一列元素之恶能从上面一个元素或者从左上元素到达因为右上元素不存在故dp[i][最后一个元素下标]min(dp[i-1][j-1],dp[i-1][j])matrix[i][最后一个元素下标]。以示例1为例计算第1行最后一个元素示意图如下↓↓ 每一行总非第1个元素和最后一个元素均可以由左上、上、右上元素向下一步到达故dp[i][j]min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j1]))matrix[i][j]。以示例1为例计算第1行下标为1的元素示意图如下↓↓ 因为我们计算到达第i行的最小路径和时需要知道第i-1行的最小路径和因此我们的计算需要从上到下。经过上面的分析我们可以得到如下代码↓↓↓
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {int n matrix.size();vectorvectorintdp(n, vectorint(n));for(int i 0; i n; i)dp[0][i] matrix[0][i];for(int i 1; i n; i){dp[i][0] min(dp[i - 1][0], dp[i - 1][1]) matrix[i][0];dp[i][n - 1] min(dp[i - 1][n - 2], dp[i - 1][n - 1]) matrix[i][n - 1];for(int j 1; j n - 1; j)dp[i][j] min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j 1])) matrix[i][j];}int ret INT_MAX;for(int i 0; i n; i)ret min(ret, dp[n - 1][i]);return ret;}
};上面代码中需要额外考虑每一行的第1个元素和最后1个元素还需要额外考虑第1行。我们可以通过对dp表多开辟1行2列来避免额外考虑上述内容。dp表第0行初始化为0这样不会影响第1行元素的计算因为min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j1]))的值始终为0。而第0列和最后一列初始化为INT_MAXint类型所能表示的最大值这样在计算min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j1]))时始终不可能选到INT_MAX所在的那一个元素因为其数值最大。新开辟的dp表示意图如下下图标注的※号位置对应于上述代码的dp表↓↓↓ 通过dp增开1行2列后的代码如下其代码行数有所缩减↓↓↓
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {int n matrix.size();vectorvectorintdp(n 1, vectorint(n 2, INT_MAX));for(int i 0; i n 1; i)dp[0][i] 0;for(int i 1; i n; i)for(int j 1; j n; j)dp[i][j] min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j 1])) matrix[i - 1][j - 1];int ret INT_MAX;for(int i 1; i n; i)ret min(ret, dp[n][i]);return ret;}
};本文存在不足欢迎留言或私信批评、指正。希望我的解决方法能够对你有所帮助~~ 今日打卡完成点亮小星星☆→★
