跟着卡哥学算法Day 32：动态规划理论 & part1

概念#

动态规划（Dynamic Programming），因此常用 DP 指代动态规划。如果某一问题有很多重叠子问题，那么使用动态规划是最有效的。

通过将问题分解为相互重叠的子问题，并利用子问题的解来高效求解原问题（利用历史记录，来避免我们重复的计算）

• 状态定义

  • 用数组表示问题的某个阶段或子问题的解，一定要明确 dp 数组dp[i][j] 代表的含义
  • 如在背包问题中，dp[i][j] 表示前 i 个物品放入容量为 j 的背包的最大价值

• 确定状态转移方程

  • 明确如何从子问题的解推导出当前问题的解，即找出数组间关系式，最难最重要的一步
  • 通俗讲就是找出 dp[i] 与 dp[i-1]、dp[i-2]之间的关系
  • 如斐波那契数列的转移方程：dp[i] = dp[i-1] + dp[i-2]

• 初始化边界条件

  • 确定初始状态的值，dp 数组的第 n 项结果由状态转移方程求解得到，所以需要知道第 n-1 项，第 n-2 项…第 1 项的值
  • 初始化 dp 数组的值，如斐波那契数列中 dp[0] = 0, dp[1] = 1

解题步骤#

动规五部曲

1. 确定 dp 数组（dp table）以及下标的含义
2. 确定递推公式
3. dp 数组如何初始化
4. 确定遍历顺序
5. 举例推导 dp 数组

为何先确定递推公式，在初始化 dp 数组呢？

因为一些情况的递推公式决定了 dp 数组要如何初始化！

动态规划如何 debug#

找问题最好的方式就是把 dp 数组打印出来，看看是不是和我们推导的公式一致。

做动规题目前，一定要把状态转移在 dp 数组上的具体情况模拟一遍，确定最后推出的是想要的结果。

题目描述#

斐波那契数，通常用  F(n) 表示，形成的序列称为 斐波那契数列 。该数列由  0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n ，请计算 F(n) 。

示例 1：

• 输入：2
• 输出：1
• 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

• 输入：3
• 输出：2
• 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

• 输入：4
• 输出：3
• 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

解题思路#

动规五部曲

1. 确定 dp 数组以及下标的含义

   dp[i] 代表第 i 个斐波那契数的值

2. 确定递推公式

   斐波那契很简单：dp[i] = dp[i-1] + dp[i-2]

3. dp 数组初始化

   dp[0] = 0, dp[1] = 1

4. 确定遍历顺序

   根据递推公式，可以看出 dp[i]依赖 dp[i - 1]和 dp[i - 2]，所以从前往后遍历

5. 举例推导 dp 数组

   按照递推公式，我们推导下 n=10 的时候，dp 数组应该是这个数列：[0,1,1,2,3,5,8,13,21,34,55]

   写代码时打印 dp 数组，看和我们推导的数组是否一致

1
var fib = function (n) {
2
  const dp = [0, 1]
3

4
  for (let i = 2; i <= n; i++) {
5
    dp[i] = dp[i - 1] + dp[i - 2]
6
  }
7

8
  console.log(dp)
9
  return dp[n]
10
}

题目描述#

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

• 输入： 2
• 输出： 2
• 解释： 有两种方法可以爬到楼顶。
  • 1 阶 + 1 阶
  • 2 阶

示例 2：

• 输入： 3
• 输出： 3
• 解释： 有三种方法可以爬到楼顶。
  • 1 阶 + 1 阶 + 1 阶
  • 1 阶 + 2 阶
  • 2 阶 + 1 阶

解题思路#

注意此处是求到达第 i 层的方法数，而不是具体的步数或花费

先确定条件，每次只能爬一层或两层楼梯，那么

• 第一层 1 种方法：1
• 第二层 2 种方法：1+1、2

爬到第三层楼梯时，只有两种方法：

1. 爬到第一层，再爬两层到第三层：1+1+1、1+2
2. 爬到第二层，直接一层到第三层：2+1
3. 那么总方法数 = 2 + 1 = 3

爬到第四层楼梯时，只有两种方法：

1. 爬到第二层，再爬两层到第四层：1+1+2、2+2
2. 爬到第三层，直接一层到第四层：1+1+1+1、1+2+1、2+1+1
3. 总方法数：2 + 3 = 5

因此，爬到第 i 层楼梯时，也只有两种方法：

1. 爬到第 i-2 层，再爬两层到第 i 层：i-2 + 2
2. 爬到第 i-1 层，直接一层到第 i 层：i-1 + 1
3. 总方法数：dp(i - 2) + dp(i - 1)

因为每一步可以选择爬 1 或 2 层，所以到达第 i 层的方法数等于到达第 i-1 层和第 i-2 层的方法数之和，所以可得递推公式 dp(i) = dp(i-2) + dp(i-1)

动规五部曲：

1. 确定 dp 数组以及下标的含义

   dp[i] 表示爬到第 i 层楼梯的方法数 （注意：是方法数，不是步数或体力消耗）

2. 确定递推公式

   dp[i] = dp[i-2] + dp[i-1]

3. dp 数组初始化

   dp[1] = 1, dp[2] = 2

4. 确定遍历顺序 从前往后

5. 举例推导 dp 数组

   当 n=5 时，dp 数组为：[1,2,3,5,8]，代码中打印一下

1
var climbStairs = function (n) {
2
  const dp = [1, 2]
3

4
  for (let i = 2; i < n; i++) {
5
    dp[i] = dp[i - 2] + dp[i - 1]
6
  }
7

8
  console.log(dp)
9
  return dp[n - 1]
10
}

题目描述#

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

**输入：**cost = [10,15,20] **输出：**15 **解释：**你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。

示例 2：

**输入：**cost = [1,100,1,1,1,100,1,1,100,1] **输出：**6 **解释：**你将从下标为 0 的台阶开始。

• 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
• 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
• 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

解题思路#

先确定条件，每次只能爬一个或两个台阶，并且需要花费相应的体力，如何到达楼梯顶部。

以[1,100,1,1,1,100,1,1,100,1]为例：

想要到达第三个台阶，可以选择：

1. 从第一个台阶开始，花费 1，到达第三个台阶
2. 从第二个台阶开始，花费 100，到达第三个台阶

此时选择花费较小的第一个选择，即 1

想要到达第四个台阶，可以选择：

1. 从第二个台阶开始，花费 100，到达第四个台阶
2. 从第三个台阶开始，花费 1，到达第四个台阶

此时选择花费较小的第二个选择，即 1 + 1 = 2

那么，想要到达第 i 个台阶时，可以选择：

1. 从第 i-2 个台阶开始，花费 cost[i-2]，到达第 i 个台阶
2. 从第 i-1 个台阶开始，花费 cost[i-1]，到达第 i 个台阶

选择花费较小的选择，即 dp[i-2] + cost[i-2] 或者 dp[i-1] + cost[i-1]

因此可以得到递推公式：dp(i) = Math.min(dp(i-2) + cost[i-2], dp(i-1) + cost[i-1])

动规五部曲

1. 确定 dp 数组以及下标的含义

   dp[i] 表示到达第 i 个台阶的最小花费

2. 确定递推公式

   dp[i] = Math.min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])

3. dp 数组初始化

   可以从下标为 0 或者下标为 1 的台阶开始爬楼梯，即dp[0] = 0, dp[1] = 0

4. 确定遍历顺序：从前往后

5. 举例推导 dp 数组

   如 cost = [1,100,1,1,1,100,1,1,100,1]，dp 数组为：[0,0,1,2,2,3,3,4,4,5,6]

1
var minCostClimbingStairs = function (cost) {
2
  const dp = [0, 0]
3
  for (let i = 2; i <= cost.length; i++) {
4
    dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])
5
  }
6

7
  console.log(dp)
8
  return dp[cost.length]
9
}