带你读《图解算法小抄》二十一、动态规划（14）https://developer.aliyun.com/article/1347948?groupCode=tech_library.
2）解题步骤
为了解决最小下降路径和的问题，我们可以使用动态规划的思想来解决。
- 定义状态：我们使用一个二维数组 dp 来表示动态规划的状态，其中 dp[i][j] 表示从第一行到第 i 行的最小下降路径和，且路径的最后一个元素位于第 i 行的第 j 列。
- 初始化状态：我们将 dp 数组初始化为一个与 matrix 数组相同大小的二维数组，并将第一行的元素复制到 dp 数组中。
- 定义状态转移方程：对于每个位置 (i, j)，我们需要考虑从上一行的哪个位置 (i-1, k) 转移而来，其中 k 的取值范围为 [j-1, j, j+1]，我们选择转移过来的路径中和最小的那个路径，即 dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])。
- 最终结果：路径的最小下降路径和将会出现在 dp[n-1][j] 中的最小值，其中 n 是数组的大小。
下面是使用动态规划解决最小下降路径和问题的算法框架：
function minFallingPathSum(matrix) { const n = matrix.length; const dp = [...matrix]; for (let i = 1; i < n; i++) { for (let j = 0; j < n; j++) { dp[i][j] += Math.min( dp[i - 1][j - 1] ?? Infinity, dp[i - 1][j], dp[i - 1][j + 1] ?? Infinity ); } } return Math.min(...dp[n - 1]); }
23.最小下降路径和
1）题目描述
给定一个大小为 n x n 的二维整数数组 matrix，找到从第一行到最后一行的最小下降路径和。每一步只能移动到下一行中相邻的元素上。在这里，相邻的元素指的是位于当前元素右下方和右下方的两个元素。
要求路径上的数字总和最小。
2）解题步骤
为了解决最小下降路径和的问题，我们可以使用动态规划的思想来解决。
- 定义状态：我们使用一个二维数组 dp 来表示动态规划的状态，其中 dp[i][j] 表示从第一行到第 i 行的最小下降路径和，且路径的最后一个元素位于第 i 行的第 j 列。
- 初始化状态：我们将 dp 数组初始化为一个与 matrix 数组相同大小的二维数组，并将第一行的元素复制到 dp 数组中。
- 定义状态转移方程：对于每个位置 (i, j)，我们需要考虑从上一行的哪个位置 (i-1, k) 转移而来，其中 k 的取值范围为 [j-1, j, j+1]，我们选择转移过来的路径中和最小的那个路径，即 dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])。
- 最终结果：路径的最小下降路径和将会出现在 dp[n-1][j] 中的最小值，其中 n 是数组的大小。
下面是使用动态规划解决最小下降路径和问题的算法框架：
function minFallingPathSum(matrix) { const n = matrix.length; const dp = [...matrix]; for (let i = 1; i < n; i++) { for (let j = 0; j < n; j++) { dp[i][j] += Math.min( dp[i - 1][j - 1] ?? Infinity, dp[i - 1][j], dp[i - 1][j + 1] ?? Infinity ); } } return Math.min(...dp[n - 1]); }
带你读《图解算法小抄》二十一、动态规划（16）https://developer.aliyun.com/article/1347938?groupCode=tech_library
