以史为鉴，不泥于史
图：本文生成式概念插画。许多来路在同一块石头上失去区别，DP 从这里开始记忆，也从这里开始遗忘。
很多条路，会在同一个位置重新相遇
夜里画一棵递归树，很容易画出一种失控的繁荣。
一只青蛙每次向前跳一格或两格。 为了数它到达第 12 块石头的方式，我们先问第 11 块和第 10 块；为了回答第 11 块，又去问第 10 块和第 9 块。 线条越分越多，可仔细一看，第 10 块石头已经在纸上出现了好几次。 每条路线都声称自己历尽艰辛，最后却站在同一块石头上，等待同一个未来。
假如从这一刻开始，之后能怎么跳只由“现在位于第几块石头”决定，那么此前绕过哪些石头已经不再重要。 那些不同历史可以合并。 第 10 块的答案算一次，后来者直接取用。
Dynamic Programming 从这种重逢开始。
它没有神奇地消灭所有选择，而是辨认出：哪些选择虽然来路不同，对未来而言已经等价。 然后用一个 state 给它们同一个名字。
DP state 不是过去的完整传记，而是未来继续决策所需的最小充分信息。
这句话里有两股相反的力量。
- 记录太少，未来无法判断 transition 是否合法； - 记录太多，每段历史都拥有独立档案，state space 又会长回 exponential size。
所以 DP 最难的部分往往不在 min、max 或那张表，而在括号里：dp( ? ) 到底需要哪些参数，才能让过去被恰到好处地遗忘。
DP 不是递归的同义词
课程用 Tower of Hanoi 开场，是因为它暴露了一种重复。
若只问移动 n 个盘子的最少步数：
两次“移动 n - 1 个盘子”的数值子问题相同，不需要分别重新求解。按 1, 2, ..., n 的顺序填表，每个 state 用常数时间得到，总共 O(n)。
当然，答案也可写成 2ⁿ - 1。但课程关心的不是这一道题的闭式，而是更普遍的观察：
- Divide and Conquer 把问题拆成相互独立的 child instances； - DP 面对 overlapping subproblems，把已经计算的答案存起来复用； - Greedy 只保留一个看起来最有希望的选择； - DP 可以枚举每个 state 的全部合法 transitions，却不重复求解相同 state。
所谓“efficient brute force”，高明之处不在 brute force，而在知道哪些分支其实走到了同一个房间。
图：State 的工作不是保存完整旅程，而是判断哪些旅程从此拥有相同的未来，作者自制。
一份 DP 答案的七个部件
COMP3121 的 DP scaffold 非常值得原样内化。
1. Instance 与 Task
我们先观察输入、输出、objective 与 constraint。 尤其区分： - counting 还是 optimisation； - subsequence 还是 substring； - at most 还是 exactly； - 可重复选还是每项至多一次； - 输出最优值还是还要输出实现它的方案。
后面一半的错误，通常在这里已经埋好了。
2. Subproblem
明确每个 state 的数学含义：
不要只写：
“答案”可能是最大值、最小代价、方案数、是否可达，也可能要求必须使用第 i 项。 差一个条件，recurrence 就会换一副骨架。
3. Recurrence
recurrence 要完成两件事：
1. 覆盖每个合法最优解的最后一步； 2. 不引入任何非法解。
通常从“最优方案最后做了什么”开始分类：
- 最后一步来自哪个 predecessor； - 最后一项选或不选； - 最后两个字符相同或不同； - 最后一次切分发生在哪里； - 路径最后一条 edge 是什么。
4. Base Cases
Base cases 是 recursion 触底时的真实语义，不是为了防止数组越界随手塞进去的数字。
例如 Hopscotch 中：
这里的 1 表示“什么都不做”也是到达起点的一种方式。若把它写成 0，后面所有方案都会因为祖先没有出生证明而消失。
5. Order of Computation
计算顺序必须尊重 dependency graph：
常见顺序包括：
- i 递增； - 一维递增、另一维任意或递增； - interval length 递增； - DAG 的 topological order； - rooted tree 的 post-order DFS； - Bellman-Ford 中允许的 edge 数递增。
6. Overall Answer
完整问题不一定恰好是最后一个 state。
LIS 的答案是：
因为最长递增子序列可能结束在任意位置，而非强制结束在 A[n]。
7. Time Complexity
最稳定的算法是：
再加上：
- 排序； - graph traversal； - data-structure operation； - backtracking； - 输出本身的长度。
若 state 数是 nC，不要条件反射写“polynomial”。C 是数值还是输入位数，后面会专门算这笔账。
为什么先陪读者走完一个例子，再让他独自走
面对空白题面，我们初学者要同时处理故事、符号、state、recurrence、边界与复杂度。 此时一句“自己想 DP”看似开放，实际上可能把工作记忆塞得像考试周的图书馆（没那么空）。
Sweller 在 1988 年关于 problem solving 与 learning 的研究中提出并以实验材料支持：对 novice新手而言，传统 means-ends problem solving 可能占用大量认知处理资源，使 schema acquisition 得不到足够空间。这不是“人脑只能记七件事”的流行简化，也不意味着探索一律有害；它提醒教学者区分两种时刻——读者是在第一次建立 representation，还是已经拥有 schema、正在练迁移。 Sweller, 1988
Worked example 也不能只是让眼睛跟着答案滑下去。Chi 等人分析学生学习 mechanics worked examples 时的 think-aloud protocols，观察到表现较好的学习者会更频繁地解释每一步为何成立、把动作连接到原理，并形成较少依赖原例的知识。 这个研究是对学习行为的细致观察，不是对所有学科的万能处方；但它给 DP 阅读提供了一个很好的问题：这一项为什么必须成为 state parameter？如果删掉它，未来哪一步失去判断依据？ Chi et al., 1989
因此，本文的例子不只给 recurrence，还刻意让支架逐渐退场：
1. Hopscotch 完整展示每个部件； 2. LIS 把难点移到 state specification； 3. Knapsack 让你发现缺失参数； 4. Edit Distance 与 graph DP 要求自己辨认 dependency shape； 5. 期末型题目只留下目标复杂度，由你决定 state。
这不是把答案喂得更慢，而是先让 representation 稳定，再把决定权还给读者。
State 设计：先问“未来还需要知道什么”
一个实用过程是：
1. 先只放足以表达 overall answer 的参数； 2. 尝试写 recurrence； 3. 若无法仅凭这些参数判断 transition 是否合法，就补充信息； 4. 若某个参数不影响任何未来决定，就删除它； 5. 重复直到 state 既够用，又不过度记录。
为什么 LIS 要求“必须结束在 A[i]”
若定义：
想从 bad(i - 1) 推出 bad(i) 时，我们不知道那个 LIS 的最后一个值，因而不知道能否接上 A[i]。
把 state 改成：
最后一个值被固定，transition 终于能判断 compatibility：
若不存在合法 j，则 len(i) = 1。按 i 递增计算。共有 n 个 states，每个检查至多 n 个 predecessors，总时间 O(n²)。
这里多加的“ends at i”不是装饰。它是 recurrence 原本缺失的那块信息。
在继续看模板前，可以停十秒：若题目要求“最长递增 substring”，还需要 max 所有 j < i 吗？如果要求 subsequence 最多允许一次下降，state 要多记哪一件未来仍会询问的事？
不必立刻写完整 recurrence。先练习判断“两个过去何时仍可合并”，DP 的表格会晚一点出现，却会更像答案而不是仪式。
来自统计学的一束侧光：足够以后，细节便可离场
统计学里的 sufficient statistic，粗略说，是把数据压缩成某个统计量，同时保留特定模型下关于参数推断所需的信息。DP state 与它有一种很有用、但需要限界的结构相似：
设计 state 时，我们也希望：
这与 Markov-style representation 的味道接近：未来只向现在询问，不逐页审查过去。
不过，普通算法 DP 不一定含概率模型，也没有自动满足统计学中关于 sufficiency 的正式定义；这里不是把 Fisher-Neyman factorization 偷渡进 Knapsack。这个旁照只带回一个更锋利的问题：
你删掉的历史细节，真的不会改变任何合法 transition 与最终 objective 吗？
若答案是否定的，就不是“压缩得很优雅”，而是 state 丢件了。
Pattern I：一维 state，常数个 transitions
Hopscotch
从 square 0 出发，每次向前 1 或 2 格，问到达 square n 的方案数。
定义：
最后一步只有两种：
Base cases：
Order：i = 2, 3, ..., n。
Answer：ways(n)。
Complexity：
- n + 1 个 states； - 每个 state O(1)； - 时间 O(n)，空间 O(n)； - 若只要最终值，保存最近两个 states 即可把空间降到 O(1)。
考场变体：青蛙只能跳 3 或 5 格
若每个 lily pad 有 frogs，目标是最大化落脚点收集的 frogs，可定义：
然后：
但不可达 state 必须表示为 -∞，否则算法可能把一条不存在的路径当成“目前价值 0 的路线”。Base cases 需要根据起点是否计分和 indices 约定仔细设定。
Pattern II：一维 state，线性个 transitions
Longest Increasing Subsequence
定义、recurrence 与复杂度为：
Correctness
取任意一个以 A[i] 结束的最优 increasing subsequence，设其倒数第二项为 A[m]。删除最后的 A[i] 后，剩余部分必须是一个以 A[m] 结束的最优 subsequence。
否则，若存在更长的、以 A[m] 结束的 subsequence，把 A[i] 接上去，就会得到一个比原方案更长、仍以 A[i] 结束的 increasing subsequence，矛盾。
recurrence 枚举所有可能的倒数第二项，并选择最好的一个，因此得到最优值。
恢复实际序列
若题目要求输出 LIS，而非只输出长度，在计算 len(i) 时同时保存：
先找到 len(i) 最大的终点，再沿 pred 向前回溯，最后反转。保存 backpointer 不改变 O(n²) 时间，只增加 O(n) 空间与 O(n) reconstruction。
Weighted Activity Selection
课程用另一个变化展示同一模板：若 activities 的目标从“数量最多”改成“总持续时间最大”，greedy earliest-finish 失效。
按 finishing time 排序后定义：
recurrence：
Answer：
排序 O(n log n)，DP O(n²)，总时间 O(n²)。
同一个 interval story，若每个活动贡献相同的 1，exchange argument 能把未来保住；若贡献变成不同 duration，DP 只好把不同终点的未来都留着。
Pattern III：容量成为 state
Unbounded Integer Knapsack
有 n 种物品，第 j 种 weight 为 wⱼ、value 为 vⱼ，每种可拿任意整数次，容量为 C。
定义：
最后一件选择为 j：
Base：opt(0) = 0。
按容量递增计算。C + 1 个 states，每个检查 n 种物品，时间 O(nC)。
因为 state 仍允许从 opt(c - wⱼ) 再次选择同种物品，所以自然表达 unbounded。
Making Change：同一张容量表，objective 换成最少硬币
给定 coin denominations，每种可无限使用，求组成 amount c 所需的最少 coins。可定义：
无法组成的 amount 记为 ∞。若有 n 种 coins、target 为 C，时间 O(nC)。它与 unbounded Knapsack 的 dependency graph 几乎相同，只是 aggregation 从 max value 换成 min count。
0-1 Knapsack：为什么必须多一个参数
若每件物品最多一次，沿用 opt(c) 会重复拿同一 item。未来还需要知道“哪些 items 仍可使用”，于是增加参数：
对第 k 件物品分类：
因此：
Base：
Order：k 递增；当前 row 只依赖前一 row。
Answer：opt(C, n)。
Time：O(nC)。
O(nC) 为什么叫 pseudo-polynomial
若容量 C 用 binary 表示，输入中写下它只需 Θ(log C) bits。运行时间 O(C) 对输入位数而言可能是指数级。
例如 C = 2ᵇ：
所以 0-1 Knapsack 的 O(nC) 是 polynomial in the numeric value C，不是 polynomial in the encoding length。复习材料特别提醒“区分值和规模”，就在防这类误判。
Balanced Partition：把“差最小”改写成接近一半
给定 positive integers，总和为 S，希望分成两组，使两组和的差最小。若一组和为 x，另一组为 S - x，差为：
于是只需在不超过 S/2 的 reachable subset sums 中找最大的 x。这可用 0-1 subset-sum DP：
时间 O(nS)，同样是 pseudo-polynomial。这个 transformation 很典型：先把 objective 写成只依赖某个 aggregate value 的式子，再决定 state 是否只需记录该 aggregate。
Pattern IV：两个序列，二维网格
两个 sequence 的 DP 常把 prefixes 放在二维表中。每个 cell (i, j) 表示前缀 A[1..i] 与 B[1..j] 的答案。
Longest Common Subsequence
定义：
若末尾字符相同：
若不同，最优 LCS 至少丢弃一个末尾字符：
Base：
共有 (n + 1)(m + 1) 个 states，每个 O(1)，总时间 O(nm)。
Subsequence 不要求连续。若题目写 substring，不能偷偷继续用这张表。
Shortest Common Supersequence
Shortest Common Supersequence 要找最短 sequence，使 A 与 B 都是它的 subsequences。可直接做 prefix DP：
时间 O(nm)。长度还满足：
因为一份 common subsequence 中的字符可被两条 sequences 共享，而其余字符必须分别保留。
Edit Distance
将字符串 A 变为 B，允许 insertion、deletion、replacement，代价分别为 cI, cD, cR。
定义：
Base：
若 A[i] = B[j]，末尾可直接匹配：
若不同，最后一步可能是：
取三者最小。时间 O(nm)，空间 O(nm)；只求距离时可滚动数组降到 O(min(n, m))，但若要恢复完整编辑序列，通常仍需 backpointers 或额外 reconstruction 技巧。
读表的几何意义
二维 DP table 可以看成 DAG：
每个 cell 的值是从起点到这里的最短路径。DP 的 row-major order，其实是在按某个 topological order 处理这张隐式 DAG。
Pattern V：Interval DP，枚举最后一次切分
Matrix Chain Multiplication
给定可相乘的矩阵序列：
矩阵乘法满足结合律，但不同括号顺序的 scalar multiplications 数量不同。
定义：
若最后一次乘法在 k 与 k + 1 之间切开：
则：
Base：
Order 不是简单的 i 递增，而是 interval length 从 1 递增。只有所有更短区间都完成，长区间才有材料可用。
States O(n²)，每个枚举 O(n) 个切分点，总时间 O(n³)。
这里的“最后一次切分”是 interval DP 最值得记住的视角：不知道最优括号长什么样没关系，所有非平凡区间都必然有一个最后合并点。
Slides 中的 “Maximising an Expression” 也属于同一类：对 expression interval (i,j) 枚举最后执行的 operator k。若包含减法、乘法或负数，仅存最大值往往不够，因为“两个最小负数相乘”可能产生最大值；此时 state 需同时保存 interval 的 minimum 与 maximum。未来需要区分的不是完整括号树，而是边界值的两端。
Graph 上的 DP：依赖关系终于显形
一张 DP table 背后常藏着 DAG。把 state 当 vertex、transition 当 edge：
- shortest path DP 对 predecessor 取 min； - longest path DP 对 predecessor 取 max； - counting DP 对 predecessor 求和； - feasibility DP 对 predecessor 做 OR。
只要 dependency graph 无环，就能按 topological order 计算。
DAG Shortest Paths
给定 weighted DAG，edge weights 可以为负。source 为 s。
定义：
recurrence：
Base：dist(s) = 0，其余初始化为 ∞。
按 topological order 处理 vertices，每条 edge 检查一次，总时间：
这里允许负 edges，因为 DAG 没有 cycle；topological order 保证一个 state 落锤后，不会有尚未处理的 predecessor 回来偷偷降价。
Assembly Line Scheduling
Assembly-line problem 也可直接画成 layered DAG。每个 station/line pair 是一个 state；从上一 stage 的同一 line 或另一 line 转入，edge weight 表示 processing 加 switching cost。
定义：
每个 state 只检查常数条 incoming transitions，因此 n 个 stages、常数条 lines 时总时间 O(n)。若还要输出换线方案，就保存 predecessor line。
Bellman-Ford：把“最多几条边”放进 state
一般 directed graph 可能有负 edges，但假设不存在 reachable negative cycle。
定义：
最后一条 edge 要么不存在新增，要么是某条 (u, v)：
simple shortest path 至多含 |V| - 1 条 edges，因此答案在第 |V| - 1 层。课程复杂度为：
再做一轮 relaxation，若仍能改进某个 reachable distance，就说明存在 reachable negative cycle。
Floyd-Warshall：把“允许哪些中间点”放进 state
求 all-pairs shortest paths。
把 vertices 编号为 1..n，定义：
最短路径要么不使用 vₖ，要么经过它：
O(n³) 个 states，每个 O(1)，时间 O(n³)。实际可将 k 维滚动掉，但解释正确性时保留三参数定义最清楚。
Tree DP
对 tree 任选 root。对每个 vertex v，state 描述 subtree Tᵥ 的答案。先处理 children，再处理 parent，因此使用 post-order DFS。
Tree DP 常需要一个额外布尔参数记录 v 是否被选择、是否被 parent 覆盖、或与 parent 的连接状态。这个参数不是为了让表看起来专业，而是让不同 subtrees 在 parent 处合并时拥有足够信息。
一道期末型建模：稳定地“挑选”不稳定的压力数据
额外复习题给出 k 名学生、n 天的压力值。第 i 天要从 k 个观测中选一个，得到序列 R[1..n]，最小化：
还要恢复具体序列，目标复杂度 O(nk²)。
State
未来的 transition 只关心“今天选了哪名学生的值”，因为明天的新增 fluctuation 只由今天值与明天值决定。
定义：
Recurrence
前一天可能选择任意学生 b：
Base：
因为第一天之前没有相邻变化。
Order：i 从 2 到 n，对每个 a 枚举全部 b。
Answer：
Reconstruction
同时保存：
从最后一层最优的 a 开始回溯，即可恢复每天选择的学生与观测值。
Complexity
- states：nk； - 每个 state 检查 k 个 predecessors； - DP 时间：O(nk²)； - backtracking：O(n)； - 总时间：O(nk²)； - 空间：若要直接回溯，O(nk)。
这个 state 没有记录前 i 天的完整序列。那会产生 kⁱ 种历史。它只记录最后一个观测的来源，因为对于明天，拥有相同“今天结尾”的两段历史，除了累计代价外已经没有区别。
Slides 末尾的 String Matching：同一模块，不是同一种 DP
官方 Module 3 slides 还覆盖 Rabin-Karp 与 KMP。它们与“保存最优子问题值”的经典 DP 不完全相同，却共享一种重要习惯：不要丢掉已经匹配得到的信息。
Rabin-Karp
对 pattern 与 text window 使用 rolling hash：
- 初始 window hash 线性计算； - 每次滑动用常数次算术更新 hash； - hash 不同则一定不匹配； - hash 相同仍应处理 collision，必要时核对原字符串。
理想/期望情形下可高效筛掉大部分窗口；最坏情况仍可能因 collisions 退化。
KMP
当匹配在 pattern 的第 j 个位置失败时，naive algorithm 把 text index 大幅退回。KMP 的 failure function 记录：
于是算法能保留这段已经确认的结构，不重新比较必然相同的字符。预处理 pattern O(m)，扫描 text O(n)，总时间 O(n + m)。
把这部分挂在 DP 博客里时，最重要的边界是：KMP 不是靠 min/max/sum recurrence 求最优值；它保存的是字符串前缀结构。模块相邻，不代表方法家族可以混叫。
如何证明一个 DP recurrence
DP correctness 不需要每次都写十页 induction，但至少要把 recurrence 的双向覆盖讲清楚。
对 optimisation recurrence，通常证明：
上界或可构造性
recurrence 枚举的每个候选，都能由一个合法 child solution 加上合法 transition 构成 parent solution。因此算法得到的值确实可实现。
下界或完备性
取任意 parent 的最优解，按最后一步分类。删除最后一步后，剩余部分落入某个 child state；若它不是该 child 的最优解，就可替换为更好的 child solution，从而改进 parent，矛盾。因此最优解一定被 recurrence 的某个候选覆盖。
再说明 base cases 正确、order 尊重 dependencies、overall answer 覆盖所有终点，证明就闭合了。
一句“由 optimal substructure 显然成立”通常正好跳过了需要解释的地方。
常见 state 设计事故
1. State 太少
dp[i] = 前 i 项的最佳答案，却无法判断第 i + 1 项能否接上。
修复：增加“最后选择了谁”“已用容量”“剩余次数”“边界状态”等未来需要的信息。
2. State 太多
记录已选完整 subset、完整路径或完整字符串。虽然 recurrence 能写，state 数却可能是 2ⁿ 或更多。
修复：问未来究竟怎样区分两段历史；若未来只看结尾、容量或少数边界，就压缩过去。
3. 选或不选时重复使用
0-1 Knapsack 的“选第 k 项”分支若回到 opt(c - wₖ, k)，就允许再次选择 k。应回到 k - 1。
4. Order 违反依赖
Interval DP 按 i 递增却没有保证较短区间完成；graph DP 在 cycle 上直接声称使用 topological order；一维空间压缩时以错误方向覆盖仍会被当前 row 使用的旧值。
5. 忘记 Overall Answer
把 len(n) 当 LIS；把“允许任意终点”误写成固定终点；把“最多容量 C”与“恰好装满 C”混为一谈。
6. Complexity 忘记 transition
n² 个 states、每个枚举 n 个 split points，总时间是 O(n³)，不是 O(n²)。表有多大，只回答了第一半。
一张考点地图
| 结构 | State 关键参数 | Transition | 时间 | |---|---|---|---| | Hopscotch | 位置 i | 常数个前驱 | O(n) | | LIS | 结尾 index i | 枚举 j < i | O(n²) | | Weighted intervals | 最后活动 i | 枚举 compatible j | O(n²) | | Unbounded Knapsack | 容量 c | 枚举物品 | O(nC) | | 0-1 Knapsack | 容量 c、前 k 项 | 选或不选 | O(nC) | | LCS / Edit Distance | 两个 prefix 长度 | 常数个邻居 | O(nm) | | Matrix Chain | 区间 (i, j) | 枚举切分点 k | O(n³) | | DAG shortest path | vertex v | incoming edges | O(V + E) | | Bellman-Ford | edge budget i、vertex v | edges | O(VE) | | Floyd-Warshall | endpoints、allowed intermediates | 用或不用 k | O(V³) | | Tree DP | subtree root、边界状态 | 合并 children | 依 recurrence |
表的用途是识别 dependency shape。真正写题时，仍要用题目自己的语义重新定义 state。
考场上的完整模板
COMP3121 偏好 plain English，而非把解释藏进 pseudocode。公式负责压缩关系，句子负责说明公式为什么覆盖所有合法解。
最后：DP 到底保存了什么？
一张 DP table 看起来像记忆。更精确地说，它是一种遗忘技术。
它忘掉路径上不再影响未来的细节，忘掉两个等价历史分别怎样走来，只留下 state parameters 与其中最好的 value。正因为忘得足够多，指数级分支才会折叠；也正因为没有多忘，recurrence 才仍然正确。
因此，遇到陌生 DP 题时，与其先寻找熟悉公式，不如问：
两段不同的过去，在什么条件下拥有完全相同的未来？
回答出来，state 就已经站在纸上了。