动态规划
动态规划不是一个算法，是一条纪律：把大问题拆成小问题，每个小问题只算一次，算完存起来。难点从来不在"怎么填表"，而在两件事——状态怎么定义，以及这个状态够不够用。这一页最后一个实验台专门演示"状态不够用"会错成什么样。
LAB 01
从递归到备忘
斐波那契：指数级的调用树，加一行缓存就变成线性
问题
递归写斐波那契只有三行，可算到第 40 项就要等好几秒——因为同一个子问题被重复算了上亿次。加一行缓存，指数变成线性。这个反差是理解动态规划最直接的入口。
模型
重叠子问题：朴素递归的调用树规模就是解本身。
T(n) = T(n−1) + T(n−2) + O(1) ⟹ T(n) = Θ(φn)
加备忘后每个子问题只算一次 ⟹ Θ(n)
动态规划能用的第一个前提就是"子问题重叠"——如果每个子问题只出现一次（比如归并排序），缓存毫无意义，那属于分治而不是动态规划。加备忘后每个子问题只算一次 ⟹ Θ(n)
朴素递归的调用次数—
加了备忘录以后—
差几倍—
朴素递归大约要跑多久—
同一个递推式，加一行缓存，指数变线性。朴素递归算 fib(30) 要 269 万次调用，算 fib(45) 要 36 亿次——已经要跑好几秒了；而带备忘录的版本，fib(45) 只要 89 次。差距在哪？重复。朴素递归里 fib(5) 会被算很多很多遍，每往下一层，重复次数翻倍。调用次数正好是 2·F(n+1)−1，按黄金比例的 n 次方增长。动态规划的第一层含义就是这个：一个问题的子问题只有 O(n) 个，而朴素递归会把它们各算 O(φⁿ) 遍。把重复算的存下来，就叫记忆化搜索（自顶向下）；按依赖顺序从小到大填表，就叫递推（自底向上）。两者等价，区别只在于要不要全部算（自底向上算全部，自顶向下只算用得到的）。判断一个问题能不能这么干，只要问一句：不同的调用路径会不会撞到同一个子问题？会撞，就有重叠子问题，缓存就有价值。
LAB 02
背包的状态表
一格一格填出那张二维表，再沿着来路把方案倒推回去
问题
背包问题是动态规划的标准模板。难点不在于写出递推，而在于想清楚"状态"应该是什么——状态选对了，转移方程几乎是自动的。这一台把那张二维表一格一格填出来。
模型
0-1 背包的状态定义与转移。
dp[i][w] = 前 i 件物品、容量 w 时的最大价值
dp[i][w] = max( dp[i−1][w], dp[i−1][w−wi] + vi )
沿着"来路"倒推就能还原出选了哪些物品——这是动态规划不只给最优值、还能给最优方案的原因。复杂度 O(nW)：注意 W 是数值不是位数，所以这是伪多项式的。dp[i][w] = max( dp[i−1][w], dp[i−1][w−wi] + vi )
最优总价值—
表格一共多少格—
暴力枚举要看多少种组合—
选中了哪几件—
这张表把"要不要装第 i 件"这个决策，变成了一次逐格比较。每一格问的是同一句话：不装第 i 件（上面那格），和装第 i 件（左上方偏移 w_i 的那格加上 v_i），哪个大？颜色越深价值越高，你能看到价值是怎么沿着"物品越多、容量越大"的方向一层层涨上去的。绿线是回溯：从右下角出发，每一步看这一格和正上方那一格是否相同——不同就说明这件装了，往左上跳。注意两个读数的对比。14 件物品时，表格只有一千多格，而暴力枚举要看 16384 种组合；把物品加到 60 件（这里滑不到，但想象一下），表格还是几千格，暴力枚举已经是 10¹⁸ 了。但这不意味着背包问题"容易"。表格大小是 n×W，而 W 是一个数值，不是输入的长度——容量写成 10 位二进制数只占 10 个字符，表格却有 1024 列。这叫伪多项式：对数值大小是多项式的，对输入长度仍然是指数的。这正是 0-1 背包既"有多项式算法"又"是 NP 难"的原因，两句话都对，只是在说不同的东西。
LAB 03
最短路与编辑距离
两个看着毫无关系的问题，状态转移方程几乎一模一样
问题
"图上找最短路"和"把一个单词改成另一个单词最少改几次"——这两个问题看上去毫无关系，写出来的状态转移方程却几乎一模一样。这一台把它们并排放，让这件事变得显然。
模型
两个问题的转移方程。
最短路：d[v] = minu→v ( d[u] + w(u,v) )
编辑距离：d[i][j] = min( d[i−1][j]+1, d[i][j−1]+1, d[i−1][j−1] + [si≠tj] )
编辑距离就是在一张 (m+1)×(n+1) 的网格图上求最短路：向右 = 删除，向下 = 插入，斜向 = 匹配或替换。看出这个同构之后，很多"新问题"其实是老问题。编辑距离：d[i][j] = min( d[i−1][j]+1, d[i][j−1]+1, d[i−1][j−1] + [si≠tj] )
编辑距离—
填了多少格—
两个词的长度—
相似度 1 − d/max(m,n)—
<
LAB 04
什么时候不能用
最优子结构与无后效性：破坏其中一条，答案就错在哪里
问题
动态规划不是万能的。它需要两个条件：最优子结构，和无后效性。破坏其中任何一条，那个看起来很对的递推就会给出错误答案。这一台造一个反例，让错误具体发生。
模型
两个前提条件的精确含义。
最优子结构：最优解包含子问题的最优解
无后效性：状态一旦确定，未来只依赖当前状态，与到达它的路径无关
当代价依赖"上一步从哪来"时，无后效性就被破坏了——这一台的转弯罚金就是这样一个例子。修法通常是把状态扩充（把"上一步"塞进状态里），代价是状态空间变大。无后效性：状态一旦确定，未来只依赖当前状态，与到达它的路径无关
只记「当前在哪」的 DP 给出的成本—
把状态扩成「上一个+当前」以后—
暴力枚举的真正最优—
结论—
这一页最重要的实验台。图还是那张分层图，只多了一条规则：每次"转弯"（上一步往上走、这一步往下走，或者反过来）要额外付钱。把转弯费设成 0，朴素 DP 永远是对的；设成 3，四十个随机实例里它错了 21 个；设成 10，错 39 个。为什么会错？因为转弯费取决于"你是从哪儿来的"，而"当前在哪个节点"这个状态里没有这个信息。这就是无后效性被破坏了：到达同一个节点的两条路，未来的代价并不相同，于是"只保留到这个节点最便宜的那条路"这个动作就是错的——被扔掉的那条路可能因为方向更顺，后面反而更省。修法只有一个方向：把缺的信息加进状态。状态从"当前节点"扩成"(上一个节点, 当前节点)"之后，读数里的第二行和第三行永远相等——我们在四十个随机实例上核对过，一次都没有例外。代价是状态数从 n 变成了边数 m。这条经验在建模里反复出现：带时间窗的路径规划要把"到达时刻"放进状态，带容量的调度要把"剩余容量"放进状态，库存问题要把"当前库存"放进状态。每加一维，正确性回来了，状态空间也炸大一圈——动态规划的全部工程难度就在这个取舍上。
这一页想说的
动态规划的两个前提：最优子结构（大问题的最优解由子问题的最优解拼出来）和无后效性（到达同一个状态之后，未来只取决于状态本身）。前者决定能不能拆，后者决定状态够不够。这一页给了三个可以带走的判断：看到重叠子问题就加缓存；把问题画成 DAG，最短路的写法就是递推式；发现 DP 算错了，几乎总是状态漏了信息，而不是转移写错了。