爱哭的赵一一

动态规划

动态规划多用来完成递归操作的逆操作，在递归中，我们求解的问题都是一样的，只是在逐渐缩小问题的规模，最终求解出我们的问题。动态规划是根据前面我们已经求解出的问题来推导出后续我们需要求解的问题。

在 leetcode 中有如下经典题目：

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶 示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

提示：

1 <= n <= 45

  • 我们思路如下：
    • 首先我们声明一个 dp 数组用来存放我们的计算结果，其中数组 dp[i]代表的是在索引 i 这个位置也就是爬 i + 1 阶楼梯的方法数，首先对数组进行初始化，直接使用 0 填充即可（其实使用什么都无所谓）。然后对爬一阶楼梯和两阶楼梯进行初始化，爬一阶楼梯就是只有一种，爬两阶楼梯就是有两种（一阶一阶爬或是一次性爬两阶）。
    • 然后开启一个循环，我们的递推公式就是dp[i] = dp[i - 1] + dp[i - 2]，使用这个公式进行填充我们的 dp 数组即可，最后返回 dp 数组的最后一项即可。
  • 代码实现如下：
    function climbStairs(n: number): number {
  const dp: number[] = new Array(n).fill(0);
  dp[0] = 1;
  dp[1] = 2;
  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n - 1];
}

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2：

输入：nums = [0,1,0,3,2,3] 输出：4 示例 3：

输入：nums = [7,7,7,7,7,7,7] 输出：1

提示：

1 <= nums.length <= 2500 -10^4 <= nums[i] <= 10^4

  • 我们的思路如下：

    • 首先创建一个 dp 数组，明确我们 dp 数组中dp[i]的含义，它代表当前i位置的上最长递增子序列是多少。
    • 我们创建一个长度与原数组长度相同的 dp 数组，然后填充 1（我们假设当前位置只有它自己是单调递增的）来将其初始化。
    • 然后开启两层嵌套 for 循环，第一层为当前的位置的值，第二次循环为开头到当前位置。我们表第一层循环的值和第二层循环的值，倘若当前位置的值大于内层循环的值那么我们就将 dp[i]替换为之前的 dp[i]和 dp[j] + 1 中较大的那个。
    • 最后返回 dp 数组中最大的那个即可。

  • 代码实现如下：

    function lengthOfLIS(nums: number[]): number {
  const dp: number[] = new Array(nums.length).fill(1);
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

该题目还有另一种使用贪心算法 + 二分算法的解法，在此不作赘述，放在 Vue 底层 diff 算法原理及实现中讲述。

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100 0 <= nums[i] <= 400

  • 我们的思路如下：

    • 题目说到不触发报警的情况下能偷到的最大金额是多少，因为我们偷任意两个连着的房子就会触发报警，所以我们只能隔一个偷，那我们要怎么做呢？
    • 首先，我们初始化一个 dp 数组，其中 dp[i]表示偷前 i-1 家能偷到的最大金额，我们使用默认值 0 来填充即可。
    • 然后，我们的递推公式中 dp[i] 的值就是 dp[i - 1] 与 di[i - 2] + 当前的金额中较大的那一个。
    • 最后，我们返回 dp 数组的最后一项即可。

  • 代码如下：

    function rob(nums: number[]): number {
  const dp = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[nums.length - 1];
}

零钱兑换（硬币找零）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2：

输入：coins = [2], amount = 3 输出：-1 示例 3：

输入：coins = [1], amount = 0 输出：0

提示：

1 <= coins.length <= 12 1 <= coins[i] <= 2^31 - 1 0 <= amount <= 10^4

  • 我们的思路如下：

    • 首先，我们声明一个 dp 数组，其中 dp[i]表示 i 元钱需要的最少硬币数，为了表示方便，我们初始化一个 i + 1 长度的数组，然后我们使用 Infinity 来填充数组。
    • dp[0]为 0。
    • 接下来我们开始循环，外层循环是硬币数 i，内层循环是要兑换的钱数 j，外层循环索引下标从 0 到硬币数的个数 -1，内层循环从当前的硬币金额开始（因为用大额的硬币永远无法构成小的钱数），一直到要兑换的金额数目。
    • 递推公式如下：
      • dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);

  • 代码实现如下：

    function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= amount; j++) {
      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示：

堆

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 示例 2：

输入：triangle = [[-10]] 输出：-10

提示：

1 <= triangle.length <= 200 triangle[0].length == 1 triangle[i].length == triangle[i - 1].length + 1 -10^4 <= triangle[i][j] <= 10^4

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

  • 我们思路如下：

    • 自上而下：
      • 首先，我们看到最小路径和以及三角形的样子，我们很容易想到使用动态规划来解决问题，我们先来初始化一个 dp 二維数组，其中 dp[i][j]表示第 i-1 层，第 j-1 个数。然后使用 Infinity 进行填充，方便后续取最小值。其中 dp[0][0]初始值就是我们的 triangle 数组的第一项中的第一个值，也就是三角形的顶点的值。
      • 接下来我们开始逐层遍历，外层循环从 1 开始即可，一直遍历到最后一层，内层循环从 0 开始一直遍历到当前层的末尾。
      • 然后我们在循环内部开始寻找递推公式，我们可以看到第 i 层的和都是由 i-1 层过来的，我们还发现第 i 层第 j 个的规律如下：
        • 当 j 为 0 也就是第一个时，当前 dp[i][j]的值就是 dp[i-1][j]的值加上当前的三角形位置的值也就是 triangle[i][j]；
        • 当 j 为最后一个时，dp[i][j]的值就是 dp[i-1][j-1]的值加上当前位置的值 triangle[i][j]；
        • 其他情况下也就是 j 在中间位置，那么 dp[i][j] 的值就是 dp[i-1][j-1]与 dp[i-1][j]的较小值再加上当前位置的值 triangle[i][j]；
      • 最后我们返回 dp 数组最后一层中的最小值即可
      • 代码实现如下：
      function minimumTotal(triangle: number[][]): number {
  const dp = new Array(triangle.length).fill([]);
  for (let m = 1; m <= triangle.length; m++) {
    dp[m - 1] = new Array(m).fill(Infinity);
  }
  dp[0][0] = triangle[0][0];
  for (let i = 1; i < triangle.length; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      if (j === 0) {
        dp[i][j] = dp[i - 1][j] + triangle[i][j];
      } else if (j === triangle[i].length - 1) {
        dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
      }
    }
  }
  return Math.min(...dp[triangle.length - 1]);
}
    • 我们还有进阶的方法，自下而上：
      • 首先，我们仍然是初始化 dp 数组，这次我们只需要一个长度为三角形最后一层的长度的数组即可，也就是长度为 triangle 数组的长度。其中 dp[i]数组表示数组第 i 层的最小值。
      • 然后我们使用 0 进行填充，然后我们外层循环从最后一层开始遍历至最上面一层；内层循环仍然是从第一个值遍历至最后一个值。
      • 接下来我们开始寻找递推公式，我们很明显可以看出来，dp[j]的值就是 dp[j+1] 与 dp[j]的最小值加上当前的值 triangle[i][j]，当然，在最后一层的最后一个时，dp[j+1]的值取不到，取不到我们直接赋值当做 0 即可，当然我们也可以在初始化的时候将 dp 数组初始化长度多增加一位即可。
      • 循环结束我们最后直接返回 dp[0]即可，此时 dp[0]就是最小的路径和。
      • 代码实现如下：
      function minimumTotal(triangle: number[][]): number {
  // 多增加1为长度，防止最后一层的最后一个值取j+1取不到
  const dp = new Array(triangle.length + 1).fill(0);
  for (let i = triangle.length - 1; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
    }
  }
  return dp[0];
}
Last Updated:
Contributors: zhao77, zhaoyuqiqi