动态规划入门讲稿：fib(5) 的朴素递归里，F₃ 被算了 2 次

课堂导读讲稿，目标受众是「计算机问题求解」课第 5 周的学生（已学过递归和分治、尚未系统学习动态规划）。讲稿定位：老师站到讲台上念的导读，不是自学教程。

同学们，今天我们讲「动态规划」（Dynamic Programming, DP）。这个名字听起来吓人——它常被讲得像一套玄学技巧。但今天讲完你会发现，DP 不是新东西，是分治这条路的亲戚；它要解决的，只是「同一件事被算了好几遍」这种最朴素的浪费。

我们这节课的节奏是：先从分治讲起，把大家已经会的东西接住；再现场演示分治卡在哪；然后讲怎么把答案记下来；接着把「dp[i] 到底在记什么、为什么这么写」讲到大家合上书能复述；再用爬楼梯到 0-1 背包把同一思路推到第二类问题；最后给一张贴在桌角的四步检查清单。

一、拆子问题这件事你早就会了——DP 是分治的亲戚，不是新东西

先问大家一个问题：你们这两周学过分治（divide and conquer），还记得它的三步吗？

第一步，把大问题拆成几个小问题；第二步，把每个小问题解出来；第三步，把小问题的答案合并起来。这就是 Manber 在《算法设计：创造性方法》第 5 章里给出的标准定义——「divide the inputs into smaller subsets, solve each subset recursively, and merge the solutions together」。Manber1989 归并排序（merge sort）、最大子数组和——这些你们上周刚做过的题，都是按这三步走的。

那么 DP 是什么？Manber 在同一本书的 §5.10（Dynamic Programming: The Knapsack Problem）里紧接着讲了一件事：Manber1989 当分治遇到「子问题被重复算了」时，朴素递归就会指数次地把同一份活翻出来重做；Manber 的原话是「The solution is to remember all the solutions and never solve the same problem twice」——把答案都记下来，永远不重算第二遍。这就是 DP 与分治的唯一差别。

请大家看下面这张 Manber 1989 年原书里给出的 0-1 背包 DP 表（Figure 5.11）。它是我们这节课要记住的一个实物形态。

图注：Manber 原书 Figure 5.11：4 行（物品大小 s_i = 2, 3, 5, 6）× 17 列（背包容量 0..16）的 DP 表。每一格三态——「I」表示找到一个含本物品的解、「O」表示找到一个不含本物品的解、「-」表示还没找到解。这就是 DP 表的物理形态：一张已经写满了答案的格子，每一格由它「上」或「左」的格子算出来。Manber1989

Manber 在 §5.10 末尾还有一句定义性的话：「The essence of dynamic programming is to build large tables with all known previous results. The tables are constructed iteratively. Each entry is computed from a combination of other entries above it or to the left of it in the matrix」——DP 的本质就是建一张「所有已知先前结果都写在里面」的大表，每一格由它上方或左侧的格子组合出来。Manber1989

英文权威教材 CLRS 在第 15 章「Dynamic Programming」里，把 Manber 的这层意思用两个标准术语钉死——具体术语名请查 CLRS 第 15 章原文，不再在本讲稿里逐字复述。这两个词大家第一次看到要有个印象，但今天讲台上的主要用语还是中文白话。

DP 这名字是谁起的？它最早出现在 1952 年 8 月美国国家科学院院刊（PNAS），由 Richard Bellman 在 RAND Corporation 工作期间命名。Bellman1952 这里的 programming 是「计划」，不是现在说的「编程」；dynamic 是 Bellman 在 RAND 时期为自己提出的方法命名时「一石二鸟」的选择——这个词在经典物理里有精确含义，而且不可能被骂成贬义词。Bellman1984 这条历史注脚记住就好，今天主线不在这里。

所以这一节一句话总结给大家：DP 不是新工具，是分治遇到「同一件事被算了好几遍」时的升级版；当子问题开始「重叠」，把答案记下来就是 DP。

二、分治卡在哪——fib(5) 的朴素递归里，同一个节点被画了好几遍

现在我们用爬楼梯（fibonacci）这道题把分治卡在哪讲清楚。题目很简单：到第 i 级台阶有多少种方案数，每次只能上 1 阶或 2 阶。

按分治思路写出来的朴素递归长这样：fib(n) = fib(n-1) + fib(n-2)。看起来没问题，跑起来也是几分钟的事——直到 n 涨上去。

我们现场把 fib(5) 这棵递归调用树展开，看看到底发生了什么。请大家看下面这张图：

图注：fib(5) 朴素递归调用树（Avik Das 2019）。根节点 F₅，向下分 F₄ / F₃，再各自向下递归展开。同一下标的节点被多次独立画出——F₃ 出现 2 次、F₂ 出现 3 次、F₁ 出现 4 次、F₀ 出现 2 次。这就是「重叠子问题」最直观的证据：同一份活被算了不止一遍。AvikDas2019

请同学们把目光放到 F₃、F₂、F₁ 这几个重复出现的节点上——同一个下标在树的不同位置被画了几遍。每个节点都是一个独立的「递归调用」，每次都把 fib(n-1) + fib(n-2) 重新跑一遍。这就是分治卡住的根本原因：当子问题之间有「重叠」（overlapping subproblems），朴素递归就会指数次地把同一份活翻出来重做。

我们再看一张英文权威图作对照——CLRS 第 15 章 Figure 15.3 rod-cutting 朴素递归调用树，n=4 时共 16 节点、8 片叶子：

图注：CLRS 第 15 章 Figure 15.3：rod-cutting 朴素递归调用树（CUT-ROD(p, n) 对 n=4 调用后的完整调用图）。根节点 4，向下分 3、2、1、0；n=4 时整棵树 16 节点 8 叶子，对应 8 种切法。原书原话：「In general, this recursion tree has 2ⁿ nodes and 2ⁿ−1 leaves」——节点数随 n 指数爆炸。Cormen

fib 这棵树 9 节点、rod-cutting 那棵树 n=4 就 16 节点——两张「爆炸的树」并排放，「重叠」这件事一秒可读。这不是 fib 独有的现象，是所有「朴素递归只盯最后一步」的问题的通病。

朴素递归到底慢到什么量级？CLRS 在 15.1 节给了一个非常具体的数字：Cormen「n = 40 takes at least several minutes, and most likely more than an hour. Each time you increase n by 1, your program's running time would approximately double」——n=40 要跑至少几分钟，n 每加 1，运行时间大约翻一倍。这就是「指数级」的实际体感。

所以这一节一句话总结给大家：朴素递归树的指数爆炸是 DP 必须修的「洞」；这个洞不只在 fib 上有，rod-cutting 等所有「朴素递归只盯最后一步」的问题上都有。从这里开始，DP 就不再是新发明，而是分治遇到重复计算时的升级方案。

三、把答案记下来——memoization 和自底向上填表是同一件事的两种写法

朴素递归既然慢在「重复算」，那最简单的修复办法就是：算过的题，把答案记下来，下次直接拿。这就是 memoization，中文常翻译成「记忆化搜索」。这一招的实质是给递归加一张 cache 表，访问过的节点直接返回值。

我们看下面这张图：

图注：Hello 算法第 14 章图 14-4「记忆化搜索对应递归树」。根节点 dp[9]，绿色实线是从根往下实际执行过的活路径（dp[9] → dp[8] → ... → dp[1]）；灰色节点加红色剪刀是被「剪掉」的子问题——遇到时 cache 命中就直接返回，不再递归。右侧两个说明框：「剪枝：找到记录，直接返回」「时间复杂度为 O(n)」。HelloAlgo

我们再放一张英文视角的对照：

图注：Avik Das Figure 2「fib 加 memo 后的剪枝图」。与上一张朴素递归树同样的 fib(5) 结构，但蓝色路径是实际执行过的递归调用，红色节点加红色 X 是「缓存命中后被剪掉」的重复子树。X 不是错误，语义是「跳过」。AvikDas2019

上面这两张图都是「自顶向下」（top-down）——从大问题 dp[9] 出发，一边递归一边把经过的子问题答案写进 cache。讲台上一画你就会发现，这种写法要画递归调用栈，黑板上不太好画。

那有没有更直观的写法？有。把视角反过来——从最小的子问题开始，按顺序往大算。这就是「自底向上填表」（bottom-up tabulation）。Hello 算法 14.1.3 节原话讲得非常清楚：HelloAlgo 「记忆化搜索是一种『从顶至底』的方法……动态规划是一种『从底至顶』的方法：从最小子问题的解开始，迭代地构建更大子问题的解」。

我们用 fib 把这两种写法串起来。先看 memoized 怎么写：

def fib(n, memo):
    if n <= 1: return n
    if memo[n] != -1: return memo[n]   # cache 命中，直接返回
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

memo 是一个 cache，「写过的题不再算第二遍」。再切到 bottom-up 怎么写：

def fib(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

dp 数组和上面那个 memo 起的是同一份「记录」作用——只是填法从「递归 + 剪枝」换成了「按顺序循环」。讲台上一画你就会发现，bottom-up 不需要画递归调用栈，黑板上直接画一列 dp[0], dp[1], dp[2], ..., dp[n] 然后一格一格填下去即可。这也是为什么课堂上我更愿意用 bottom-up 来讲。

为什么可以按顺序填？关键在「同一棵树压成图」。Avik Das 把 fib 那棵递归树「压平」成一张图，每个节点只画一次——这就是 DAG（directed acyclic graph，有向无环图）：

图注：Avik Das Figure 3「fib DAG」。6 个圆圈节点水平等距分布 F₀ 到 F₅；箭头一律从大指向小（F₅ → F₄ → ... → F₀）；多条弧形绕过上方或下方使多个右侧节点汇入同一个左侧节点（fan-in 结构）。同一节点只画一次，多个父节点汇入同一个子节点——这就是递归树压成图的几何形状。AvikDas2019

DAG 有一个非常关键的几何性质：「线性化」——你可以把所有顶点按一个顺序排开，让箭头始终顺着这个顺序从前往后指。Avik Das 在博客里把这条性质写得很直白：AvikDas2019「DAGs have the property of being linearizable, meaning that you can order the vertices so that if you go through the vertices in order, you're always following the direction of the arrows」。

翻译成 DP 的语言：你可以把所有子问题从小到大排个顺序（fib 里就是 F₀ → F₁ → ... → Fₙ），按这个顺序填表，每填一行时，左边依赖的格子已经填过了。这条性质直接解释了为什么 bottom-up 能按顺序填。

所以这一节一句话总结给大家：memoization（自顶向下）和自底向上填表在教学上是两种写法（top-down 走递归，bottom-up 走循环），但在 DP 本质上是同一件事——用同一个 cache / dp 数组记录子问题答案，避免重复计算。

四、状态与状态转移——dp[i] 到底在记什么、为什么这么写

前三节我们已经走完了「DP 是分治升级版」「分治卡在重复计算」「记答案就解决」。但还有一个核心问题没讲清楚：dp[i] 到底在记什么？

这三个 DP 术语是绕不开的——我们用 Hello 算法 14.1.3 节末尾给的白话翻译，一次讲清：HelloAlgo

• dp 表（状态表）：dp 数组。dp[i] 表示状态 i 对应子问题的解——用爬楼梯的话说，dp[i] 就是「到第 i 级台阶有多少种方案」。
• 初始状态：最小子问题对应的状态。dp[1] = 1, dp[2] = 2——爬到第 1 级只有 1 种走法，第 2 级有「1+1」或「直接 2」两种。
• 状态转移方程：从一步推出下一步的递推公式。dp[i] = dp[i-1] + dp[i-2]。

这三句白话可以原样搬到讲台上。

我们再讲清「为什么是 dp[i] = dp[i-1] + dp[i-2]」。Hello 算法 14.1.1 节给了一句话讲清：HelloAlgo「由于每轮只能上 1 阶或 2 阶，因此当我们站在第 i 阶楼梯上时，上一轮只可能站在第 i-1 阶或第 i-2 阶上。换句话说，我们只能从第 i-1 阶或第 i-2 阶迈向第 i 阶」。

换句话说，到第 i 级的「最后一步」只有两种走法——从第 i-1 级跨 1 阶上来，或从第 i-2 级跨 2 阶上来。两种走法互不重叠，方案数直接相加——这就是「加法型」状态转移方程能写出来的根本原因。

请大家看下面这张递推关系图：

图注：Hello 算法第 14 章图 14-2「方案数量递推关系」。三层错位方块：底层绿色是 dp[3] 与 dp[4]，上层蓝色是 dp[5]，箭头表示 dp[5] = dp[3] + dp[4] = 8。底部是方案数表 1, 2, 3, 5, 8, 13——每一格的答案由它上方紧邻的两格相加得到。HelloAlgo

这张图是 dp[i] = dp[i-1] + dp[i-2] 的视觉锚点：两个更小的格子的答案相加 = 当前格子的答案。一秒可读。

现在讲一个 labuladong 在中文 DP 教程里反复强调的解题框架——labuladong「明确『状态』→ 明确『选择』→ 定义 dp 数组/函数的含义」三步。爬楼梯这三步对应到：

• 状态：dp[i] = 到第 i 级的方案数；
• 选择：最后一步只有两种——从第 i-1 级跨 1 阶，或从第 i-2 级跨 2 阶；
• dp 数组含义：按顺序从小到大填，每一格由它左上方相邻两格相加。

labuladong 在同一篇教程里把这句话点得很重——「写出状态转移方程是最困难的」labuladong。本专题第 4 节是高潮，就是为了攻这一关。

英文权威 CLRS 在 15.1 节给的状态转移方程形式是：Cormen r_n = max_{1≤i≤n} (p_i + r_{n-i})——把 rod-cutting 的状态转移写成一个 max 取最大。爬楼梯的加法型对照过来是 dp[i] = dp[i-1] + dp[i-2]，对应 CLRS 的 (15.1)(15.2) 那种结构。两套写法形式不同，本质是一样的——「这一步可以由哪几种上一步推出来」。

所以这一节一句话总结给大家：先想 dp[i] 是哪一件事的答案（状态），比写代码重要一百倍——状态定义错了，状态转移方程和填表顺序全错。「最后一步只有几种走法」是状态转移方程能写出来的根本原因。

五、从加法型到决策型——爬楼梯升级到 0-1 背包

爬楼梯这一类题，归在一起叫「加法型 DP」——dp[i] = dp[i-1] + dp[i-2]，把所有可能的「最后一步」方案数加起来。但不是所有题都能「加起来」。

0-1 背包就属于另一类——决策型 DP。题面：给定 n 件物品和容量 cap 的背包，每件物品只能选一次，求能装的最大价值。状态：dp[i, c] = 只看前 i 件物品、背包容量剩 c 时的最大价值（这是二维下标，第一次出现）。状态转移方程：HelloAlgo

$$dp[i, c] = \max(dp[i-1, c],\ dp[i-1, c - wgt[i-1]] + val[i-1])$$

加法型是「把所有走法加起来」，决策型是「在两个互斥方案里取较大」。白话翻译：装不下 → 不取（第二项不存在）；装得下 → 取与不取选较大（取 max 的语义）。

请大家看下面这张图：

图注：Hello 算法第 14.4 节图 14-20 step7 帧「0-1 背包问题的动态规划过程」。左侧是物品表（wgt/val 三行：🍎 1,5 / 🍍 2,11 / 🍉 3,15）；右侧是 4 行 × 5 列二维 dp 表，列上方是 5 个递增的手提袋图标（容量 0..4）。i=2 行 c=2 写作 11 并浅绿高亮；带 +11 标注的浅蓝箭头从 dp[1, 0]=0 斜向指向 dp[2, 2]=11，对应公式第二项 dp[i-1, c-wgt[i-1]] + val[i-1]——「装得下 → 取较大」那一支。底部给出完整公式。HelloAlgo

这条 +11 箭头正是「装得下 → 取较大」那一支在 dp 表上的样子：当前格 dp[2, 2] 取的是「左上方格 dp[1, 0] 的 0 + 当前物品 val=11」。爬楼梯是「加」，背包是「取 max」——开关就在这一步。

接着讲空间优化。注意到 dp[i, c] 只依赖 dp[i-1, *]（上一行），所以整个 dp 表可以压成一个一维数组 dp[c]。但这里有个关键细节——内层循环必须倒序遍历。为什么？我们看下面这张图：

图注：Hello 算法第 14.4 节图 14-22 step3 帧「0-1 背包的空间优化后的动态规划过程」。底部文字「倒序遍历第 i = 2 行，进行状态转移」+ 展示压缩后的一维数组 dp = [0, 5, 5, 16, 16]。蓝/绿箭头分别演示「自身引用」（c=2 → c=1，蓝）与「跨行 +11 引用」（c=3 的 16 ← c=1 的 5 + val=11）。HelloAlgo

如果正序遍历，从 c=0 到 c=cap，写完 dp[c] 后会覆盖掉 dp[上一行][c-w]（即左上方格），下一轮算 dp[c+w] 时就读不到原本的 dp[上一行][c] 了。倒序遍历就是「先算右边的、再算左边的」，保证每个 dp[c] 读到的是「上一行」还没被覆盖的旧值。HelloAlgo

把这一节和上一节连一下：爬楼梯的「加法」换成了背包的「取最大」——核心思路完全一样（按顺序填表、子问题答案可复用），只是合并方式从「加法」换成了「取较大」。同学们写一道新 DP 题时，先把状态定下来（dp[i] = 哪件事的答案），再看「最后一步有几种走法」——加法型就把所有走法加起来，决策型就在所有走法里取最大。

我们把爬楼梯和 0-1 背包对比一下：

这一节一句话总结给大家：dp[i] = dp[i-1] + dp[i-2] 是加法型的代表（爬楼梯这类「数有几条路」的题），dp[i, c] = max(...) 是决策型的代表（0-1 背包这类「怎么选」的题）。两者共享「状态」这条定义，同样「最后一步只有几种走法」的思路，只是把「加法」换成「取最大」。

六、拿到题先想什么——一张贴在桌角的四步检查清单

同学们，我们把 labuladong 三步框架（"明确状态"、"明确选择"、"定义 dp 数组/函数的含义"）化用为本讲台的四步检查清单。labuladong 这张清单是拿到一道新 DP 题后，按这个顺序挨个想清楚再动手写代码——而不是先写代码再补状态。

请把这四步贴到课桌角上：

1. 状态是什么——dp[i]（或 dp[i, c]）在记哪一件事的答案？这一步最重要，错了后面全错。
2. 转移是什么——dp[i] 由哪些更小的状态推出？写出公式。
3. 初值是什么——最小子问题的答案是什么？这一步是 labuladong 三步里没有的、由 Hello 算法 14.1.3 节末「初始状态」补出。HelloAlgo
4. 顺序是什么——按什么顺序填表？这一步保证算到 dp[i] 时，它依赖的更小状态都已经填好了。

我们把这四步和上一节的爬楼梯对一下：

不在这张清单上的，就是你还没想清楚。

课后我推荐两件事。第一，自己进浏览器开 VisuAlgo 的 /en/recursion 模块（新加坡国立大学 NUS Steven Halim 团队自 2011 年维护至今的算法可视化平台）VisuAlgo，按 §4-1 Fibonacci Numbers (Tree) 和 §4-2 Fibonacci Numbers (DAG) 切来切去，看 fib(4) 的递归树长什么样、再看 DAG 里重复节点是怎么消失的；0-1 背包走 §4-5 / §4-6 同构路径。

第二，关注一下近年 DP 教学工具的研究方向。下面这张图来自一篇 2024 年 11 月提交 arXiv 预印本（arXiv:2411.07705）、正式发表于 SIGCSE TS 2025 的工具论文：

图注：Lee et al. (2024) dpvis 论文 Fig. 2。左栏带行号的 Python 循环代码，右栏按 WRITE 操作切分出的「逻辑流」子序列，再右栏是一维数组 arr 逐格染色（每个单元格填入时刻标有 READ → READ → WRITE 小箭头）。dpvis 把「按顺序从小的往大的算」这件事画给你看。dpvis2024 这条研究线的具体含义是：把 Python 内置的 List 替换成 DPArray、在结尾调一次 display，就能给现有 DP 程序加上「按帧切分」的逐帧动画和「下一帧会读 / 写哪些格子」的自测题。

论文报告了一个本科课程 162 人规模、24 份自愿问卷的部署：dpvis2024 18/24 受访学生认为 dpvis 帮助理解了「子问题数组」的作用——也就是说，把填表过程逐帧画出来，对「子问题答案被记下来」这件事的理解是有帮助的。不过作者自己也声明这个样本量统计意义有限，只是作为「可视化教学方向有人在做」的一条近期信号。

这一节一句话总结给大家：拿到 DP 新题，先按「状态 → 转移 → 初值 → 顺序」四步想清楚再写代码；课后自己去 VisuAlgo 玩一遍 fib 树与 DAG；学术界正在把这件事做得更可视化，但本课核心是「清楚想明白四步」——可视化只是把你想明白的东西画给你看。

参考文献

本专题引用的核心资料如下，建议深入学习时阅读原文：

1. Bellman, R. (1952). On the Theory of Dynamic Programming. Proceedings of the National Academy of Sciences 38(8): 716-719 — PMC1063639（DP 一词的首次学术发表）
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.), Chapter 15 Dynamic Programming — §15.1 Rod cutting — PDF（英文教材章节切片；Figure 15.3 递归树、Figure 15.4 DAG、公式 (15.2)）
3. Manber, U. (1989). Introduction to Algorithms: A Creative Approach, Chapter 5 §5.10 Dynamic Programming: The Knapsack Problem — archive.org（分治三步定义 + DP 本质定义 + Figure 5.11 knapsack DP 表）
4. krahets (持续维护至 2026). Hello 算法 第 14.1 节「初探动态规划」 — hello-algo.com（爬楼梯 dp[i]=dp[i-1]+dp[i-2] + 图 14-2 递推关系 + 图 14-4 记忆化搜索 + 三个术语白话翻译）
5. krahets (持续维护至 2026). Hello 算法 第 14.4 节「0-1 背包问题」 — hello-algo.com（0-1 背包状态转移方程 + 图 14-20 step7 + 图 14-22 空间优化）
6. labuladong. 动态规划解题套路框架 — labuladong.github.io（明确状态→明确选择→定义 dp 三步框架）
7. Das, A. (2019). A graphical introduction to dynamic programming — avikdas.com（fib 朴素递归树、memo 剪枝图、DAG 三张图）
8. Halim, S. et al. (2011–). VisuAlgo — Recursion Tree and DAG Visualization — visualgo.net/en/recursion（交互式教学平台；§4-1/§4-2 Fibonacci Tree↔DAG、§4-5/§4-6 0-1 Knapsack Tree↔DAG）
9. Lee, D. H., Prasad, A., Deo-Campo Vuong, R., Wang, T., Han, E., Kempe, D. (2024). dpvis: A Visual and Interactive Learning Tool for Dynamic Programming. SIGCSE TS 2025 — arXiv:2411.07705（DP 逐帧动画 + 自测题工具研究；本科 162 人部署 + 24 份问卷）