Sherfiter's wiki for fun

第 10 章 · 动态规划与贪心

动态规划(DP)吓退过无数人,因为它总被讲成「状态转移方程」的咒语。其实 DP 只是一个诚实观察的结果:很多递归会反复计算同一个子问题,算过的存起来就行了。第 9 章末尾留的问题(斐波那契为什么指数级)就是它的引子。本章先建方法论(两大前提 + 备忘录),再用背包和 LCS 两个母题练出写状态的手感,最后请出贪心:当问题「不用考虑全局」时,连表都可以不建,每步抓最大即可。三者的分界线画清,这一章的魂就定了。

10.1 递归为什么爆炸:重叠子问题

朴素递归的斐波那契,fib(5) 的调用树:

                 fib(5)
               /        \
          fib(4)         fib(3)
         /      \        /     \
     fib(3)   fib(2)  fib(2)  fib(1)
     /    \    ...      ...
 fib(2) fib(1)

fib(3) 被算了 2 次,fib(2) 被算了 3 次,规模越大重复越严重,T(n) = T(n-1) + T(n-2) 指数增长。而每次调用的「实际工作」只有一次加法,真正不同的子问题只有 n 个。重复计算把 n 个问题放大成了 2ⁿ 次调用,这是病根。DP 的药方同样简单:第一次算完存表里,之后再遇到直接查。指数到线性的差距,全部来自这一张缓存表。

由此提炼 DP 的两个前提:子问题重叠(才有缓存价值,区别于第 9 章分治的「独立子问题」)、最优子结构(大问题的最优解由子问题的最优解拼成,才能从小到大构造)。验证一道题能不能 DP,先验证这两条,再谈状态设计。

10.2 0/1 背包:状态设计的母题

n 件物品,每件重 w[i] 值 v[i],背包容量 W,求最大总价值(每件至多选一次)。直接说设计结果:

状态:dp[c] = 容量 c 时能装下的最大价值
转移:dp[c] = max(不选第 i 件: dp[c],
                  选第 i 件:   dp[c - w[i]] + v[i])

二维版(前 i 件物品、容量 c)最好理解,压成一维后有个必须吃透的细节:内层倒序遍历 c:

int knapsack(int *w, int *v, int n, int W) {
    int *dp = calloc(W + 1, sizeof(int));
    for (int i = 0; i < n; i++)
        for (int c = W; c >= w[i]; c--)      // 倒序!
            if (dp[c - w[i]] + v[i] > dp[c])
                dp[c] = dp[c - w[i]] + v[i];
    int ans = dp[W];
    free(dp);
    return ans;
}

倒序的原因画一遍就懂:正序时 dp[c - w[i]] 已经是「本轮更新过的」,相当于第 i 件物品被算了两次(变成了完全背包);倒序保证读到的 dp[c-w[i]] 还是「上一件物品时代的」,每件只选一次。这个「遍历方向改变语义」的细节是背包家族(完全背包正序、0/1 背包倒序、分组背包再套层)的全部奥义,写错不报错、只是答案错,全靠手推小样例验证。

DP 的通用思考路径,拿这道题当模板记:定义状态(答什么问题)→ 找转移(当前决策如何拼子问题)→ 定边界(最小的子问题)→ 定遍历顺序(保证算到某状态时它依赖的状态已就绪)。四步走完,写出代码只是体力活。

10.3 LCS:二维状态与决策表

最长公共子序列(X 和 Y 的公共部分最长能多长,不要求连续)。状态天然二维:

dp[i][j] = X 前 i 个、Y 前 j 个的 LCS 长度
转移:X[i-1] == Y[j-1] ? dp[i-1][j-1] + 1
                       : max(dp[i-1][j], dp[i][j-1])

逐格填表,X 的每个字符和 Y 的每个字符各比一次,O(n·m)。填完表从右下角回溯(相等则收下这对字符、往左上走,否则往大的方向退)可以还原出具体的公共子序列本身。「编辑距离」「最长公共子串」都是这张表的亲戚,套路完全一致:两个序列逐格对齐,每个格子的决策只有「收下或跳过」。

10.4 贪心:连表都不建的勇气

贪心的策略极端大胆:每一步只看当前,拿局部最优,不回头。找零(面额 100/50/20/10/5/1):每次拿不超过余额的最大面额,全局也最优。区间调度(最多不重叠区间):按结束时间排序,每次选最早结束且不冲突的,证明思路是「最早结束的区间,给后面留的空间一定不比别的选择少」(交换论证)。

但贪心是带前提的武器:只有「局部最优能推出全局最优」(贪心选择性质)时才正确。反面教材就在找零:面额改成 {1, 3, 4}、金额 6,贪心拿 4+1+1 用三枚,最优是 3+3 两枚。贪心错时不报错、只给次优答案,这比崩溃更阴。所以顺序是:先试图证明贪心(通常靠交换论证:把任何最优解逐步换成贪心的选择,值不变),证不出来,老老实实回 DP(找零在任意面额下就是背包)。

三者的分界表,值得默写:

方法子问题关系每步决策典型
分治独立不重叠合并子解归并、快排
DP重叠建表记状态背包、LCS
贪心不回溯局部最优区间调度

判断顺序也是做题顺序:能贪(能证)先贪,证不了贪再看重叠(重叠 DP、独立分治)。图论章的 Dijkstra、Prim 已经是贪心的应用,Kruskal 的切分定理就是一次标准的交换论证,现在回头看那两章,你会发现自己已经在用贪心的语言思考了。

常见错误

  • 背包正序遍历。0/1 背包写成正序,退化成完全背包(物品无限件),答案悄悄变大。拿小例子(1 件重 1 值 1,容量 3)手推一遍正序错误。
  • 状态定义含糊。dp[i] 到底「以 i 结尾」还是「前 i 个」?一字之差,转移完全不同(最大子段和两个版本都存在)。定义写注释里,再写代码。
  • 贪心不证明直接交。比赛里贪心错全盘错,工程里贪心错是资损。证不出「局部最优 ⇒ 全局最优」就用 DP 兜底。

练习

  1. 手算:背包 W=10,物品 (w,v) = (5,6) (4,7) (3,5),手推 dp 表全过程,给出最优解和选中物品(回溯)。
  2. 手算:求 "ABCBDAB" 与 "BDCABA" 的 LCS(填完整表,回溯出子序列)。
  3. 动手:实现「完全背包」(物品可无限选,内层正序),和 0/1 版本对比在同样输入下的答案差异,造一个能看出差异的最小用例。
  4. 思考:找零 {1,3,4} 金额 6 的贪心失败,请用 DP 解同一问题(它就是「面额物品、价值 1」的完全背包最小枚数版),并总结「什么特征的面额系统贪心才安全」(提示:想想标准硬币系统和「倍增」结构)。
豫ICP备2026027944号