25. 爬楼梯的秘密（动态规划）

知识点：动态规划（dynamic programming）—— 把重复算过的问题记下来（记忆化）

项目：爬楼梯 + 最少硬币（对比贪心！）

---

故事开场：楼梯到底有几种走法？

你家的楼梯有 10 级台阶。老师说：

"每次可以上 1 级或 2 级台阶。从地面到 10 级台阶， 一共有多少种不同的走法？"

你蹲在楼梯口数了起来：

• 1 级台阶：只能"上 1 级"——1 种
• 2 级台阶："1+1"或"直接 2"——2 种
• 3 级台阶："1+1+1"、"1+2"、"2+1"——3 种
• 4 级台阶：你蹲得腿都麻了——5 种

"1、2、3、5……"你念叨着，"这数字有点眼熟啊？"

咦，这不就是第 15 章挑战过的爬楼梯问题吗！规律是：

到第 n 级台阶，要么从第 n−1 级上 1 级，要么从第 n−2 级上 2 级。 所以 f(n) = f(n−1) + f(n−2)，而 f(1) = 1，f(2) = 2。

你信心满满地写了个递归版（第 15 章的套路）：

// 爬楼梯：递归版（f(n) = f(n-1) + f(n-2)）
function climbStairsRec(n: number): number {
  if (n <= 2) {
    return n              // 出口：1 级 1 种，2 级 2 种
  }
  return climbStairsRec(n - 1) + climbStairsRec(n - 2)
}

console.log("10 级：" + climbStairsRec(10) + " 种走法")

输出：

10 级：89 种走法

算对了！你得意地想多算几级——"试试 45 级！"

console.time("递归算 45 级")
console.log("45 级：" + climbStairsRec(45) + " 种走法")
console.timeEnd("递归算 45 级")

然后，你盯着屏幕……1 秒、2 秒、10 秒……程序还在"想"！

算 10 级只要一眨眼，算 45 级却要 10 秒！ 这不对劲——问题出在哪？

---

笨办法先行：同一个楼梯，算了一遍又一遍！

把"算 45 级"的调用过程画出来，你就明白了：

f(45) = f(44) + f(43)
f(44) = f(43) + f(42)      ← f(43) 又出现一次！
f(43) = f(42) + f(41)      ← f(42) 已经出现两次了！
...

f(43) 被算了 2 遍，f(42) 被算了 3 遍，f(30) 被算了几万遍…… 整个调用树长得像两棵互相纠缠的大树——同一个答案，被反复计算 无数次！算 45 级，总共要算约 37 亿次 f(…)！

这就是"递归 + 不记答案"的代价：指数级爆炸（O(2ⁿ)）。

你气得跺脚："明明算过一次 f(30) = 1346269 了，第二次要算的时候 直接拿出来用不就行了？！"

——等等，你说什么？"算过的，记下来，下次直接拿"？ 你刚才无意中说出了动态规划的核心思想！

---

引出知识点：动态规划——算过的答案，记下来

**动态规划（dynamic programming，简称 DP）**的秘诀只有一句话：

把算过的答案记下来，下次用到直接拿，不再重算。

实现方法有两种，殊途同归：

方法一：记忆化递归（自顶向下）——递归照写，但加一个"小本本"：

const memo: number[] = []      // 小本本：memo[n] = f(n) 的答案

function climbStairsMemo(n: number): number {
  if (n <= 2) {
    return n
  }
  if (memo[n] !== undefined) {      // 算过了？直接拿！
    return memo[n]
  }
  memo[n] = climbStairsMemo(n - 1) + climbStairsMemo(n - 2)
  return memo[n]
}

console.time("记忆化算 45 级")
console.log("45 级：" + climbStairsMemo(45) + " 种走法")
console.timeEnd("记忆化算 45 级")

输出：

45 级：1836311903 种走法
记忆化算 45 级: 0.1ms

0.1 毫秒！ 从几十秒变成 0.1 毫秒——因为每个 f(n) 只算一次， 一共只算 45 次！这就是记忆化的魔法：用一点内存（小本本）， 换回指数级的时间。

方法二：填表格（自底向上）——从最小的开始，一格一格往上填：

function climbStairsDP(n: number): number {
  const ways: number[] = []        // ways[n] = f(n)
  ways[1] = 1
  ways[2] = 2
  for (let i = 3; i <= n; i++) {
    ways[i] = ways[i - 1] + ways[i - 2]   // 用前面两个格子的答案
  }
  return ways[n]
}

console.log("45 级：" + climbStairsDP(45) + " 种走法")

输出：

45 级：1836311903 种走法

"填表格"的思路更直接：从已知出发，一步步推出未知—— 1 级 1 种 → 2 级 2 种 → 3 级 = 2+1 = 3 → 4 级 = 3+2 = 5 → 5 级 = 8 → 6 级 = 13 → ……一路填到 45 级。

（注意：1836311903 已经快到 2³¹ 了——再往大算，又会撞上 第 1 章说过的"大数记不准"，你就知道该去找"大数"工具了！）

---

动手实现：最少硬币——动态规划 vs 贪心

还记得上一章的"贪心翻车"吗？硬币 1/3/4，凑 6 元，贪心 3 枚， 最优 2 枚。现在用动态规划正面打败它！

思路（填表格）：best[i] = 凑出 i 元最少要几枚硬币。

• best[0] = 0（0 元不用凑）
• 凑 i 元：最后一步可以是 1 元、3 元或 4 元的硬币 → best[i] = 1 + min(best[i-1], best[i-3], best[i-4]) （只从"够得着"的硬币里选！）

const coins = [1, 3, 4]      // 刁钻的币制

// 动态规划：凑出 amount 元最少要几枚硬币
function minCoinsDP(amount: number): number {
  const best: number[] = []
  best[0] = 0

  for (let i = 1; i <= amount; i++) {
    best[i] = Infinity                 // 先假设凑不出来
    for (let c = 0; c < coins.length; c++) {
      if (i >= coins[c]) {
        // 用一枚 coins[c]，剩下的 i - coins[c] 用 best 里的答案
        const count = best[i - coins[c]] + 1
        if (count < best[i]) {
          best[i] = count
        }
      }
    }
  }

  return best[amount]
}

console.log("凑 6 元最少 " + minCoinsDP(6) + " 枚")    // 2（3+3）
console.log("凑 10 元最少 " + minCoinsDP(10) + " 枚")  // 3（3+3+4）
console.log("凑 47 元最少 " + minCoinsDP(47) + " 枚")  // 12（4×11+3）

输出：

凑 6 元最少 2 枚
凑 10 元最少 3 枚
凑 47 元最少 12 枚

DP 赢了！ 6 元 → 2 枚（3+3），正是贪心找不到的答案。

best[i] 只依赖"更小的 i"的答案——这就是"填表格"的精髓： 大问题的答案，由小问题的答案拼出来；小问题的答案，早就填在表格里了。

---

跑起来：DP vs 回溯，比比谁快

第 24 章的回溯版 minCoinsBrute 能算最优，但慢；DP 也能算最优，还快。 比一比凑 47 元：

// 回溯版（第 24 章的）和 DP 版都来算 47 元
console.time("回溯凑 47 元")
const brute = minCoinsBrute(47)
console.timeEnd("回溯凑 47 元")

console.time("DP 凑 47 元")
const dp = minCoinsDP(47)
console.timeEnd("DP 凑 47 元")

console.log("回溯 " + brute + " 枚，DP " + dp + " 枚")

在我这台电脑上，输出（数字可能不一样）：

回溯凑 47 元: 约 89 秒！
DP 凑 47 元: 约 0.2ms

89 秒 vs 0.2 毫秒——差了 40 万倍！ 同样的 47 元，回溯要试 3^47 种组合（每一种都试），DP 只填 47 个格子。把金额改成 500， 回溯直接卡到天荒地老（3 的 500 次方，宇宙毁灭都试不完）； DP 填 500 个格子，0.5 毫秒搞定。金额越大，DP 的优势越恐怖。

为什么回溯慢、DP 快？ 回溯把"凑 45 元"的答案算了 3 遍 （因为 46、47、48 元都可能用到它）；DP 只算 1 遍，存在 best[45] 里。不重复劳动，就是动态规划的全部秘密。

动态规划三步走：

1. 找状态：用什么表示"小问题"？（爬楼梯：到第 n 级；硬币：凑 i 元）
2. 找递推式：大问题怎么用小问题拼？（f(n) = f(n-1) + f(n-2)）
3. 填表格：从最小的问题开始，一格一格往上填

背包问题、最短路径、字符串匹配……无数难题都是这三步的变体。 你已经是"会填表"的人了！

---

小挑战

1. 一次上 3 级：如果每次能上 1、2 或 3 级，f(n) 的规律是什么？ 用 DP 算 20 级有几种走法（提示：f(n) = f(n-1) + f(n-2) + f(n-3)， 出口 f(1)=1、f(2)=2、f(3)=4）。

2. 数字三角形：下图的数字三角形，从顶上走到底，每次只能走 左下或右下，经过的数字和最大是多少？

       5
      7 8
     2 3 4
    4 9 6 1

   （提示：best[行][列] = 数字 + max(左上来的, 右上来的)—— 从最后一行往上填，这是经典 DP 题！）

3. 记忆化 vs 填表：把爬楼梯的"记忆化递归"和"填表格"都写一遍， 想一想它们各自的优点（提示：记忆化只算用得到的；填表更省心， 不会栈溢出）。

---

课后练习

第 1 题（动手题）：走方格

一个 3×3 的网格，从左上角走到右下角，每次只能向右或向下走一格， 一共有多少种不同的走法？（提示：到 (行, 列) 的走法数 = 到 (行−1, 列) 的 + 到 (行, 列−1) 的——又是爬楼梯的亲戚！用 DP 填表。）

参考答案（点开查看）

// ways[行][列] = 到这一格的走法数
const ways: number[][] = []
for (let x = 0; x < 3; x++) {
  ways.push([0, 0, 0])
}

// 第一行、第一列都只有 1 种走法（一直向右 / 一直向下）
for (let y = 0; y < 3; y++) { ways[0][y] = 1 }
for (let x = 0; x < 3; x++) { ways[x][0] = 1 }

// 其余格子 = 上面来的 + 左边来的
for (let x = 1; x < 3; x++) {
  for (let y = 1; y < 3; y++) {
    ways[x][y] = ways[x - 1][y] + ways[x][y - 1]
  }
}

console.log(ways[2][2])   // 6

填出来的表格：

1 1 1
1 2 3
1 3 6

到右下角一共 6 种走法。这个"走方格"问题，就是背包问题、 路径规划的老祖宗——而它只是爬楼梯换了个样子！

第 2 题（思考题）：为什么 DP 不重复劳动？

回忆一下：递归版 climbStairsRec(45) 和 DP 版 climbStairsDP(45)， f(30) 分别被算了几次？

参考答案（点开查看）

• 递归版：f(30) 被算了几万次——每一条从 45 通到 30 的路 都要重算一遍（调用树是爆炸的）
• DP 版：f(30) 被算了1 次——填表格时填一次，之后每次用到 都直接从 ways[30] 里拿

"算一次，存起来，用一百次"——这就是动态规划的核心。 代价只是多花一点点内存（一张小表格），省下的是指数级的时间。

第 3 题（思考题）：贪心、回溯、DP 三兄弟

现在三种方法你都学过了。给下面的问题选方法，并说说理由：

① 25/10/5/1 币制找零 ② 迷宫寻路 ③ 任意币制找零（凑 500 元） ④ 活动安排（选最多活动）

参考答案（点开查看）

① 贪心：币制整齐，贪心就是最优，还最快。 ② 回溯：路有多条、选错会死，必须试遍所有路（也可以用 BFS！ 下一章就学）。 ③ 动态规划：币制刁钻（贪心会错），金额又大（回溯会卡死）， 只有 DP 又快又稳。 ④ 贪心："结束最早"就是最优（每步都有把握），不需要 DP。

选方法的口诀：先试贪心（快）→ 找到反例就换 DP（快且稳）→ 实在没有递推式才用回溯（稳但慢）。大多数时候，DP 是"最优解"的 最优选择——这也是"动态规划"四个字里"规划"的含义： 把每一步都规划好，不浪费一次计算。

---

下一课预告：坐地铁！你要从"家"站去"游乐园"站，地铁线路图 像一张网。老师问："最少坐几站能到？"——用 DFS 乱走？ 可能绕远路。第 19 章的层序遍历有个秘密：它天生就是 "一圈一圈扩散"的。地图上的"一圈一圈"，就是"一站一站"……