动态规划

动态规划（DP）是两个性质的组合：重叠子问题（同一个子问题被反复求解）与最优子结构（问题的最优解由子问题的最优解构成）。前者使分治失效，后者使记忆化有效。本章从记忆化讲起，给出状态定义的方法论与空间优化。

从斐波那契说起

朴素递归 $F(n) = F(n-1) + F(n-2)$ 是 $O(2^n)$ ——大量重复计算。两个等价的修法：

from functools import lru_cache

# 自顶向下：记忆化
@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# 自底向上：迭代填表
def fib_bottom_up(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

两者都是 $O(n)$ ：自顶向下（记忆化）保持递归结构，按需计算；自底向上按依赖顺序填表，可以顺手做空间优化。自顶向下写起来快，自底向上省空间省递归开销。

状态定义的方法论

DP 的一切在状态定义。标准套路：

定义状态： $dp[i]$ （或 $dp[i][j]$ ）表示什么问题的答案？好的状态定义让转移自然出现。常用视角：前缀（ $dp[i]$ = 前 $i$ 个元素的答案）、以 i 结尾（ $dp[i]$ = 以第 $i$ 个元素结尾的最优答案）、区间（ $dp[i][j]$ = 区间 $[i, j]$ 的答案）、剩余容量/状态集（背包、状态压缩）。
写转移方程：最优解的最后一步如何由更小的状态构成？
定边界与答案位置。
确定计算顺序（或直接记忆化）。

背包

0/1 背包： $n$ 个物品、容量 $C$ ， $dp[c]$ = 容量 $c$ 下的最大价值，转移

dp[c] = \max(dp[c],\; dp[c - w_i] + v_i) \quad (\text{容量倒序遍历，防止重复选取}).

$O(nC)$ ——伪多项式（ $C$ 是数值不是位数），这也是背包是 NP 难但能解的重要原因（→ NP 完全问题与近似算法）。

最长公共子序列（LCS）与编辑距离

$dp[i][j]$ = 前 $i$ 与前 $j$ 个字符的答案：

\text{LCS:}\quad dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & s_i = t_j \\ \max(dp[i-1][j], dp[i][j-1]) & \text{否则} \end{cases}

编辑距离（Levenshtein）是同一框架， $\min$ 换 $\max$ 、加插入/删除代价 $1$ 。两者是 diff 工具（git diff 的内核）与拼写纠错的原理， $O(nm)$ 。

区间 DP 与状态压缩

区间 DP： $dp[i][j]$ 由更短的区间合成（矩阵链乘法、石子合并），按区间长度顺序计算， $O(n^3)$ ；
状态压缩：集合作为状态（ $dp[\text{mask}]$ ）， $O(2^n n)$ 顶得住 $n \le 20$ ——指数复杂度但比 $n!$ 好得多，旅行商的精确解法。

空间优化：滚动数组

若 $dp[i]$ 只依赖 $dp[i-1]$ （或上一行），旧状态可以丢：滚动数组把二维压成一维。LCS 与背包都能压到 $O(n)$ 或 $O(C)$ 。更极端时（斐波那契）压到两个变量。原则：转移只看最近几步时，表就只需要最近几步。

识别 DP 问题的信号

问"最优值"（最长、最短、最大、最少）而非具体方案；
有最优子结构：整体最优由局部最优构成（贪心更强的信号是"局部最优即全局最优"，见贪心）；
有重叠子问题：朴素递归会重复计算；
决策之间相互影响（不能独立取局部最优）。

本章要点

DP = 重叠子问题（使分治失效）+ 最优子结构（使记忆化有效）
先写出递归关系，再考虑求解顺序；状态定义决定一切
自顶向下写起来快，自底向上省空间省递归；滚动数组把二维压成一维
背包是伪多项式 $O(nC)$ ：数值与位数之别（→ NP 完全性）
区间 DP $O(n^3)$ 、状态压缩 $O(2^n n)$ ：n ≤ 20 的集合问题顶得住