带你读《图解算法小抄》二十一、动态规划（15）

带你读《图解算法小抄》二十一、动态规划（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