CSCI3160 L06 递归陷阱与动态规划

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L06 递归陷阱与动态规划 · 原件 L06-DP-01-Pitfall-of-Recursion-未核-隐藏.pdf（本地课件） p.1–9 定位：用同一个递推分别写递归和填表，找到指数时间来自哪里，并把重复子问题只算一次。承接：#L01-01 递归原则

p.1 标题页。

动态规划加速的对象（p.2–3）【新】

p.2 dynamic programming, which is a technique for accelerating recursive algorithms.

p.2 所说的“programming”不是编程语言。动态规划不改变子问题的数学答案，改变的是组织计算的方法。

题面（L06-DP-01-Pitfall-of-Recursion-未核-隐藏.pdf · Problem · p.3）

p.3 Problem: Let A be an array of n positive integers. Consider function Goal: Compute f(n).

公式按讲义重排：

f(k)=\begin{cases}0&k=0,\\\max_{1\le i\le k}(A[i]+f(k-i))&1\le k\le n.\end{cases}

表（题面，p.3）：原数组。

i	1	2	3	4
A[i]	1	5	8	9

$k$ 是待解决规模， $i$ 是枚举的选择， $k-i$ 是依赖的更小规模；max 表示所有合法选择中取最好一个。算一遍： $f(1)=1+0=1$ ； $f(2)=\max(1+1,5+0)=5$ ； $f(3)=\max(1+5,5+1,8+0)=8$ ； $f(4)=\max(1+8,5+5,8+1,9+0)=10$ 。每个 max 都必须比较全部候选，不是看到第一个不错的就停止。

朴素递归为什么指数慢（p.4–6）【延伸 L01 p.4】

p.4 直接照式子递归：每个 f(k) 循环调用 f(k-1) 到 f(0)，取最大和。结果正确，但同一个 f 值会沿不同调用路径反复求。

p.4 的完整朴素版本如下，特意保留与填表版相同的候选比较，便于看清变快发生在哪里：

f(k):
  若 k = 0：返回 0
  ans = 负无穷
  for i 从 1 到 k：
    tmp = A[i] + f(k-i)
    若 tmp > ans：ans = tmp
  返回 ans

p.5 How many times do we need to call f(0) in computing f(1), f(2), ..., and f(6), respectively?

将计算 f(k) 时进入 f(0) 的次数记为 C(k)，且 C(0)=1。因为 f(k) 调用全部更小规模， $C(k)=\sum_{j=0}^{k-1}C(j)$ 。于是 C(1)=1，C(2)=1+1=2，C(3)=1+1+2=4，C(4)=8，C(5)=16，C(6)=32。每加一个规模，之前所有叶调用又复制一遍。

p.4 写出的下界是 $\Omega(2^n)$ 。从这些次数可以证明它：对 k≥2， $C(k)=\sum_{j=0}^{k-1}C(j)$ ，而 $C(k-1)=\sum_{j=0}^{k-2}C(j)$ ，两式相减得 $C(k)-C(k-1)=C(k-1)$ ，即 $C(k)=2C(k-1)$ 。由 C(1)=1 得 $C(n)=2^{n-1}$ ；仅进入基本情形已经花这么多次，全部执行当然至少是指数级。这里 C 统计零规模调用，不是函数值 f；不能将 f(4)=10 与 C(4)=8 混为一谈。

p.6 的陷阱就是重复子问题，不是“递归语法本身慢”。只需计算 n+1 个不同的函数值，却走了指数多次重复调用；只数不同参数值，会严重低估朴素算法时间。

记住答案，再按依赖顺序求解（p.7–8）【新】

p.7 Resolve subproblems according to a certain order. Remember the output of every subproblem to avoid re-computation.

p.7 的原则有两个部分：保存每个结果；先算依赖项。p.8 从 $f(0)=0$ 开始，依次算 f(1)、f(2)、…、f(n)。在计算 f(k) 时，所有 k-i 都小于 k，所以数组查询替代递归调用。

第 k 个状态枚举 k 个选择，总代价为 $1+2+\cdots+n=n(n+1)/2$ 次候选计算，即 $O(n^2)$ 。本例 n=4 共 $1+2+3+4=10$ 次候选比较，结果仍为 1、5、8、10。改变了运行时间，没有改变递推定义。

补充：把一棵调用树压成依赖图。 计算 f(4) 的根会直接请求 f(3)、f(2)、f(1)、f(0)；其中 f(3) 又请求 f(2)、f(1)、f(0)。参数相同的 f(2) 在固定数组 A 下答案相同，没有理由算第二次。记忆化做法保留递归写法，但进入 f(k) 时先检查“是否已算”；命中直接返回，未命中才枚举 k 个候选并存结果。与自底向上填表相比，二者计算的状态相同，本例总时间同为平方量级。

这个缓存的键不只是抽象的 k，而是“当前固定价格数组下的 k”。换了数组 A 后不能继续复用上一题缓存，否则例如原 A[2]=5 改成 100 后仍返回旧 f(2)=5。实现中最好每个输入新建缓存，或者显式清空。

自测：有 n 个状态，是否说明时间是 O(n)？

本例不是。状态 f(k) 需检查 k 个第一段，故总工作为 $\sum_{k=1}^n k$ 。缓存消除了重复求同一状态，却没有让“一个状态内部要试多少选择”消失。反过来，若只数候选而漏掉昂贵的复制或字符串操作，也可能低估实现成本。

从递推落到表（p.9）

p.9 define special value ans[0] ← 0

讲义用 ans[k] 存 f(k)，每轮先设为负无穷，再把每个 A[i]+ans[k-i] 与它比较。负无穷表示“尚未看过任何候选”，不是一个实际价格。0 号单元是已定义的空问题；实现需保留 n+1 个下标位置，不能越界读取 ans[0]。

ans[0] = 0
for k 从 1 到 n：
  ans[k] = 负无穷
  for i 从 1 到 k：
    ans[k] = max(ans[k], A[i]+ans[k-i])
输出 ans[n]

考试角度：（A 级：Midterm-2021T1-题目.pdf Q3 与 Review-Quiz-2020T2-题目.pdf Q5，考保存递推状态及更新顺序；演练见附录 A1）。

本讲核心考点

识别重复子问题，而不是把递归一概判为低效（p.4–6，C 级）。
f(0)调用次数为1、2、4、8、16、32（p.5，C 级）。
填表时间等于各状态转移数之和（p.8–9，C 级）。
状态覆盖前保留后续仍需的旧值（对应两道递推填空，A 级）。

附录

A1 作业/往年题演练（非讲义内容）：两个变量保存递推

题面（Midterm-2021T1-题目.pdf · Q3 · p.1）

p.1 3. [4 points] Function g(n) is defined by $g(n)=2g(n-1)+g(n-2)$ for $n\ge2$ with initial values g(0) = 1 and g(1) = 2. Fill in the missing parts in lines 2 and 5 of the following algorithm for computing g(n): input n; x ← [blank]; y ← [blank]; for i = 1 to n do y ← 2y + x; x ← [blank]; end for; output y.

公式按原题重排；方括号标记原卷的空白。循环从 i=1 开始，先令 y=g(0)=1；为了第一轮得到 g(1)=2，必须令 x=0。更新 y 后还要让 x 保存旧 y，因为下一轮需要前一项。旧 x 加 2 倍旧 y 等于新 y，所以旧 y=(新 y−旧 x)/2；最后一空可填 (y-x)/2。

逐轮核验：初始 (x,y)=(0,1)；i=1 后先 y=2，再 x=1；i=2 后 y=5、x=2；i=3 后 y=12、x=5。输出 1、2、5、12 与递推完全一致。n=0 时循环不执行，输出 1，也符合边界。

题面（Review-Quiz-2020T2-题目.pdf · Q5 · p.1）

p.1 5. Function g(n) is defined by $g(n)=3g(n-1)-g(n-2)$ for $n\ge2$ with initial values g(0) = 1 and g(1) = 2. Correct two errors in the following algorithm for computing g(n): input n; x ← 1; y ← 2; for i = 1 to n do y ← 3y − x; x ← y; end for; output y.

公式按原题重排。初始已经有 g(0)、g(1)，第一轮应生成 g(2)，所以循环应从 i=2 到 n。第二个错误是 x←y 把刚计算的新项也放进 x，丢失旧项；应先暂存旧 y，算新 y，再将旧 y 放到 x，或把该行改为 x←(y+x)/3。

核验：初始 (1,2)；i=2 得新 y=3·2−1=5，旧 y=(5+1)/3=2；i=3 得新 y=3·5−2=13，旧 y=(13+2)/3=5。于是连续状态为 (1,2)、(2,5)、(5,13)，每轮都保存相邻两项。若输入允许 n=0，还需直接返回 1；题面循环修正适用于 n≥1，不能把基本情形丢掉。

已读官方题解采用另一组恰好两处修改：保留循环 i=1 到 n，把初值 y 改为 1，末行改为 x←(x+y)/3。由 g(1)=3g(0)−g(−1) 可反推扩展值 g(−1)=1，所以初值 (x,y)=(1,1) 正好保存 g(−1)、g(0)。第一轮得到 (1,2)，第二轮得到 (2,5)，第三轮得到 (5,13)；n=0 直接输出 1。这是与原卷两个修改位置完全相符、也覆盖零输入的版本。

回到正文：从递推落到表（p.9）

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L06-DP-01-Pitfall-of-Recursion-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。