【动态规划】LeetCode-931.下降路径最小和

🎈算法那些事专栏说明：这是一个记录刷题日常的专栏，每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新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列的元素，可以到达第i+1行第j-1列、第i+1行第j列、第i+1行第j+1列元素。如下图左图所示，第0行第1列元素可以到达第1行第0列、第1行第1列、第1行第2列元素。也就是说，当前元素向下走时，可以向左下走、向下走或者向右下走。反过来说，到达第i行第j列的上一步可以是第i-1第j-1列、第i-1行第j列、第i-1行第j+1列，如下图右图所示。
在这里插入图片描述
题目中所说的最小路径是指：从第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][j+1])+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][j+1]))+matrix[i][j]。以示例1为例，计算第1行下标为1的元素示意图如下↓↓

因为我们计算到达第i行的最小路径和时，需要知道第i-1行的最小路径和，因此，我们的计算需要从上到下。经过上面的分析，我们可以得到如下代码↓↓↓

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>>dp(n, vector<int>(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][j+1]))的值始终为0。而第0列和最后一列初始化为INT_MAX（int类型所能表示的最大值），这样在计算min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))时，始终不可能选到INT_MAX所在的那一个元素，因为其数值最大。新开辟的dp表示意图如下，下图标注的※号位置对应于上述代码的dp表↓↓↓
在这里插入图片描述
通过dp增开1行2列后的代码如下，其代码行数有所缩减↓↓↓

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>>dp(n + 1, vector<int>(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;}
};