DP 不是公式库

DP 最容易被学成公式库。背包一套公式，LIS 一套公式，LCS 一套公式。

这样短期有用，但遇到变体很容易崩。

更好的理解是：把所有 DP 问题看作 DAG 上的最短路、最长路或最优路径问题。

状态是节点，决策是边，递推是在沿着边传播最优值。

所以 DP 设计的核心问题是：

  • 状态里必须记住哪些信息
  • 哪些状态依赖哪些更小状态
  • 依赖关系有没有环
  • 每个状态从哪些候选转移取 min / max

DP 四步

看到一个 DP 问题，按顺序落实四步。

第一步：定义子问题

这是最关键的一步。常见定义方式：

  • $T[k]$：以第 $k$ 个元素结尾的最优值
  • $T[k,l]$：只看前 $k$ 个物品、容量为 $l$ 的最优值
  • $T[i,j]$：子串 $S[i..j]$ 上的最优值
  • $T[u]$：DAG 上从 $u$ 到终点的最优值

状态定义必须能唯一确定一个子问题。信息少了，递推不成立；信息多了，状态空间爆炸。

第二步：明确最后一步决策

DP 的递推通常来自最后一步：

  • 最后一个元素取还是不取
  • 最后一条边从哪里来
  • 最后一个活动选不选
  • 区间最后一次合并在哪里切
  • 最后一个字符来自字符串 A 还是 B

如果说不清最后一步，就很难写出可靠递推。

第三步：写递推关系

把每一种合法决策对应的候选值列出来，取 max 或 min。

常见形式是：

$$ dp[i] = \min_j \{dp[j] + cost(j,i)\} $$

或者：

$$ dp[i] = \max_j \{dp[j] + value(j,i)\} $$

第四步：确定 base case 和计算顺序

Base case 是最小子问题。填表顺序必须保证每个状态被计算时，它依赖的状态已经算完。

这就是拓扑序。

自顶向下 memoization 和自底向上 table filling，本质上都是在同一个依赖 DAG 上计算。

Knapsack：容量是状态的一部分

0/1 Knapsack 的输入是物品重量 $w_i$、价值 $v_i$、容量 $C$。每个物品最多选一次，目标是最大化总价值。

状态定义：

$$ T[k,l] = \text{只考虑前 } k \text{ 个物品，容量为 } l \text{ 时的最大价值} $$

最后一步决策：第 $k$ 个物品选不选。

递推：

$$ T[k,l] = \max( T[k-1,l], T[k-1,l-w_k]+v_k ) $$

第一项是不选第 $k$ 个物品，第二项是选第 $k$ 个物品。

这里状态里必须有容量 $l$。只知道“考虑前 $k$ 个物品”不够，因为剩余容量决定后面还能不能选。

复杂度：

$$ O(nC) $$

这个复杂度是 pseudo-polynomial。因为 $C$ 是数值大小，不是输入长度。若 $C$ 用二进制表示，输入长度只包含 $\log C$。

DP 变体通常是加维度

很多 DP 变体并不需要新思想，只是状态要多记一点。

两个背包：

$$ T[k,C,D] $$

表示考虑前 $k$ 个物品，两个背包剩余容量分别为 $C$ 和 $D$。

物品分两类：

可以增加一个维度记录两类数量差、已经选了多少类，或者约束是否满足。

最多出现 $s$ 次下降：

$$ T[i,s] $$

表示以第 $i$ 个元素结尾，并且已经用了 $s$ 次下降的最优值。

这种模式很常见：原问题有一个额外限制，就把限制变成状态的一部分。

但加维度会增加状态数量。DP 不是免费午餐，状态越多，复杂度越高。

LIS：以谁结尾

Longest Increasing Subsequence 的关键状态是“以某个元素结尾”。

定义：

$$ T[k] = \text{以 } a[k] \text{ 结尾的最长递增子序列长度} $$

最后一步：在 $a[k]$ 前面接某个 $a[j]$，要求 $j

递推：

$$ T[k] = 1 + \max\{T[j] \mid j如果没有合法 $j$，则 $T[k]=1$。

最终答案是：

$$ \max_k T[k] $$

这里状态不定义成“前 $k$ 个元素的 LIS”也可以，但“以 $k$ 结尾”更容易转移。状态设计的原则是：它要方便描述最后一步。

常见变体：

  • 限制间隔：只允许 $j$ 在 $k-1,k-2,k-3$ 中
  • 限制值差：要求 $|a[j]-a[k]| \leq B$
  • 奇偶交替：要求 $a[j]+a[k]$ 为奇数
  • 求最大和：把长度换成总和

它们都沿用同一个状态，只是合法前驱集合变了。

LCS：二维前缀

Longest Common Subsequence 的状态通常是：

$$ T[i,j] = \text{字符串 } x[1..i] \text{ 和 } y[1..j] \text{ 的 LCS 长度} $$

最后一步看最后两个字符：

如果 $x[i]=y[j]$：

$$ T[i,j]=T[i-1,j-1]+1 $$

如果 $x[i]\neq y[j]$：

$$ T[i,j]=\max(T[i-1,j],T[i,j-1]) $$

这个状态的含义很自然：两个前缀之间的最优匹配。

二维 DP 很多时候都来自“两个序列的前缀”。编辑距离、字符串交错、sequence alignment 都是类似结构。

区间 DP：子串或子数组上的最优值

区间 DP 的状态一般是：

$$ T[i,j] = \text{区间 } [i,j] \text{ 上的最优值} $$

适用于问题天然定义在一个连续片段上，比如回文、括号、矩阵链乘法、合并成本。

一个典型递推：

$$ T[i,j] = \min_k \{T[i,k] + T[k+1,j] + cost(i,k,j)\} $$

这里最后一步是把区间 $[i,j]$ 切成两段。

区间 DP 的填表顺序通常按长度递增：

length = 1, 2, 3, ...

因为 $T[i,j]$ 依赖更短区间。

不能连续选超过 k 个

这类题的约束是相邻结构。

比如不能连续选取 3 个，定义 $T[i]$ 为前 $i$ 个位置的最大价值。

最后几步可能是：

  • 不选第 $i$ 个
  • 选第 $i$ 个，不选 $i-1$
  • 选第 $i$ 和 $i-1$，不选 $i-2$

递推：

$$ T[i]=\max( T[i-1], a_i+T[i-2], a_i+a_{i-1}+T[i-3] ) $$

如果约束是不能连续选 $m$ 个，就把分支扩展到最多连续选 $m-1$ 个。

这类题的重点是把“连续选了几个”这件事在最后一步里展开，或者直接把连续数量作为状态维度。

Interleave / Shuffle

字符串交错问题问：字符串 $C$ 是否可以由 $A$ 和 $B$ 交错形成，并保持 $A$ 和 $B$ 各自内部顺序。

状态：

$$ T[i,j] = \text{A 的前 } i \text{ 个字符和 B 的前 } j \text{ 个字符能否组成 C 的前 } i+j \text{ 个字符} $$

最后一个字符来自 A 或 B：

$$ T[i,j] = (A[i]=C[i+j] \land T[i-1,j]) \lor (B[j]=C[i+j] \land T[i,j-1]) $$

这里不需要第三维 $k$，因为 $k=i+j$ 已经确定。状态里不要放冗余信息，这会让表变大。

Weighted interval scheduling

无权活动选择可以 greedy，按结束时间最早选。

有权活动选择就不行。一个长活动价值很高，可能比多个短活动更好。

这时用 DP。

把活动按结束时间排序。定义：

$$ T[k] = \text{只考虑前 } k \text{ 个活动时的最大价值} $$

最后一步：第 $k$ 个活动选不选。

若选第 $k$ 个活动，就只能接在某个与它不冲突的最后活动后面。设 $p(k)$ 是结束时间不超过第 $k$ 个活动开始时间的最大索引。

递推：

$$ T[k] = \max(T[k-1], v_k + T[p(k)]) $$

这个例子很适合说明算法选择：无权版本有 greedy-choice property，有权版本需要记录更多历史，所以变成 DP。

DP 正确性怎么写

DP 正确性证明通常用 induction。

结构大概是：

  1. Claim：$T[\cdot]$ 的定义确实表示对应子问题的最优值
  2. Base case：最小状态正确
  3. Inductive hypothesis：假设所有更小状态都已经正确
  4. Inductive step：证明当前状态的递推覆盖所有合法最后一步，并且每个候选都合法

例如 knapsack：

  • 任意最优解要么不选第 $k$ 个物品，要么选第 $k$ 个物品
  • 不选时，价值是前 $k-1$ 个物品容量 $l$ 的最优解
  • 选时，剩余容量是 $l-w_k$，价值是前 $k-1$ 个物品容量 $l-w_k$ 的最优解再加 $v_k$
  • 两种情况取 max 就覆盖了所有可能

这比直接写公式更重要。公式只是结果，证明解释为什么状态足够。

DP 的复杂度

DP 复杂度通常这样算：

状态数量 × 每个状态的转移成本

例子：

问题状态数量每个状态成本总复杂度
Knapsack$nC$$O(1)$$O(nC)$
LIS 基础版$n$$O(n)$$O(n^2)$
LCS$nm$$O(1)$$O(nm)$
区间切分 DP$n^2$$O(n)$$O(n^3)$

如果递推里有一个 $\max_j$ 或 $\min_j$，通常每个状态要扫一圈。优化 DP 很多时候就是减少这个转移成本。

什么时候不要用 DP

DP 适合有重叠子问题和最优子结构的问题。

如果子问题之间没有重叠，分治可能更自然。

如果局部选择已经足够，并且能用 exchange argument 证明，greedy 更简单。

如果状态必须记录一个指数级集合，比如 TSP 的 subset DP，DP 也许能做，但复杂度会很高。

DP 的价值在于把指数级搜索压缩成多项式数量的状态。压缩是否成功，取决于状态能不能保留足够信息，又不保留太多信息。

这也是 Part II 的核心：DP 的关键在状态设计，递推只是状态依赖的结果。