算法 07：动态规划的状态、转移与方案恢复

看到递推式之后，动态规划往往只剩几层循环；真正困难的部分发生在写循环之前：哪些历史可以合并成一个状态，哪些信息会影响未来，怎样让每个前驱先于当前状态计算完，压缩空间之后还能不能找回方案。

本篇通过背包、最长递增子序列、最长公共子序列和硬币计数，把这些判断逐一展开。完整 C++17 源码与文中算法对应，包含独立小规模枚举校验；运行入口见数据结构与算法学习路线。

一、状态设计：留下未来需要的信息

假设若干物品有重量和价值，每件最多使用一次，要恰好装满重量 W 并使总价值最大。把“当前已装多少重量”记为状态还不够：处理到第几件物品决定了后面还可以选择什么。

令 dp[i][w] 表示：只使用前 i 件物品，恰好装出重量 w 的最大总价值。这句话同时规定了候选范围、约束和目标。“有一个数组 dp”没有这些语义，后续每一步都无法检查。

同一个状态可以由很多物品组合到达。只要这些组合已经处理相同的前缀、当前重量相同，它们面对的剩余物品就相同；在价值可以直接相加的前提下，价值更小的组合不会优于价值更大的组合，因此只保留最大价值即可。

这也是状态压缩的依据：丢弃的历史必须不影响未来的可行选择和收益。若新增“相邻选择的物品不能同色”，最后一次选中的颜色就影响下一步；两个同重量、同前缀的方案未必还能合并，需要记录最后颜色等信息。

一个错误状态怎样暴露

设下一件物品是红色，两个历史方案都已装到重量 4；其中一个最后选了红色，另一个最后选了蓝色。它们的合法后继不同。即使红色历史价值更高，也不能直接覆盖蓝色历史，否则可能丢掉能选下一件红色物品的最优方案。

状态应包含什么，取决于问题约束。物品是否只能用一次、是否要求恰好装满、是否有颜色限制，都会改变递推；这也是不能按题目里出现“背包”两个字就套代码的原因。

动态规划可以记忆化递归，也可以按依赖顺序填表。本篇使用填表，便于直接检查状态来源；搜索与贪心篇说明枚举决策如何扩展成搜索树，这里则合并会遇到相同后续问题的节点。

二、0/1 背包：初始化与循环方向都属于语义

三件物品分别为 A=(重量 2，价值 3)、B=(3，4)、C=(4，5)，目标 W=5。每件最多选择一次，价值相加，没有额外选择限制。

恰好装满不能把整张表初始化为 0

没有物品时，重量 0 可达，价值为 0；重量 1、2、3 等全部不可达。若把它们也初始化为 0，就凭空允许了“已经免费装出这些重量”的历史。

数学上可以用负无穷表示不可达。源码限定所有物品价值非负，所以选择 unreachable=-1；它与合法价值 0 不冲突，且只在可达前驱上进行加法。若允许负价值，−1 就不再适合作为哨兵，需要独立可达标记或 std::optional。

处理第 i 件、重量为 wi、价值为 vi 时，候选有两个：

• 不选：继承 dp[i−1][w]。
• 选一次：若 w≥wi 且前驱可达，取 dp[i−1][w−wi]+vi。

两者取最大值；都不可达时保持不可达。用“—”表示不可达，逐行计算得到：

在 B 行的 w=5，选 B 的候选是上一行 w=2 的 3 加上 B 的价值 4，得到 7。C 行无法改进：选 C 要求上一行 w=1 可达，但它不可达。因此答案是 A+B，总价值 7。

如果题目改成“总重量不超过 W”，空方案就对每个容量上限都合法；常见状态是“容量上限 w 的最优价值”，所有容量初始化为 0。另一种做法是保留本篇的精确重量状态，最后在 dp[n][0..W] 中取最大值。两种定义都能使用，但必须前后一致。

一维压缩：为什么必须倒序

第 i 行只依赖第 i−1 行，所以可以用一维数组保存价值。现在数组同时承载旧行和新行，遍历方向负责保证读取的是哪一行：

std::vector<Value> dp(static_cast<std::size_t>(capacity) + 1, unreachable);
dp[0] = 0;
for (const auto& item : items) {
    for (int w = capacity; w >= item.weight; --w) {
        if (dp[w - item.weight] != unreachable)
            dp[w] = std::max(dp[w], dp[w - item.weight] + item.value);
    }
}

倒序处理时，较小的 w−item.weight 尚未被本轮修改，读取的仍是上一行，因此本件最多使用一次。该片段对应 knapsack01_value；返回值用 std::optional<Value> 区分不可达与合法的价值 0。

错误反例只需要一件物品 (2,3) 和目标 W=4。若正序遍历，先把 dp[2] 更新为 3，再用这个刚更新的值把 dp[4] 更新为 6；同一件物品被用了两次。正确的 0/1 答案是不可达。

如果物品每种可以使用无限次，这个正序依赖恰好是需要的：dp[w−wi] 可以已经包含本种物品，继续加一件就能使用多次。源码 knapsack_complete_value 仅把重量循环改为从 wi 增大到 W，同一反例现在合法，答案就是 6。

完全背包要求重量为正。若允许重量 0 且价值为正，最优价值无界；不能继续使用这段有限表递推。源码直接拒绝非正重量。

只保存价值还不够恢复物品

knapsack01_restore 保存二维表，从 (n,W) 往前走：

• 若 dp[i][w]==dp[i−1][w]，可以不选第 i 件。
• 否则本状态依靠选第 i 件获得，记录下标，再令 w-=wi。
• 每一步 i 都减一，最后反转记录的下标。

相同最优价值可能对应多套方案；源码在平局时优先不选当前物品，返回其中一套，并不承诺字典序最小。

直接给一维数组附上可变的 parent[w]，容易把不同轮次的历史串在一起。仍看物品 A=(2,3)、B=(2,4)、目标 4：处理 B 时，先使 dp[4]=7，它依赖处理 B 之前的 dp[2]=3；随后 dp[2] 被 B 改为 4。如果恢复时只读取当前 parent[2]，就可能把 B 记录两次。二维表保留了“来自哪一行”。

物品数 n、目标重量 W：价值版时间 O(nW)、空间 O(W)；二维恢复版时间和空间均为 O(nW)。这是按 W 的数值计的伪多项式时间，W 的二进制位数只有 O(log W)，所以“对 W 线性”不代表对输入编码长度线性。源码限制 n≤200、W≤5000、价值≤1000000，计算使用 64 位整数。

三、最长递增子序列：从清楚的状态到更小的代表

输入 [3,1,2,2,4]，求严格递增子序列的最大长度。子序列允许跳过元素，但保持原下标顺序；重复的两个 2 不能同时放进严格递增序列。一个答案是 [1,2,4]，长度 3。

O(n²)：定义为“以谁结尾”

令 length[i] 表示以第 i 个元素结尾的最长严格递增子序列长度。每个元素单独成序列，所以初值都是 1；前驱只可能是 j<i 且 a[j]<a[i] 的位置。

for (std::size_t i = 0; i < a.size(); ++i) {
    for (std::size_t j = 0; j < i; ++j) {
        if (a[j] < a[i] && length[j] + 1 > length[i]) {
            length[i] = length[j] + 1;
            parent[i] = j;
        }
    }
    if (length[i] > length[last]) last = i;
}

这段循环来自 lis_quadratic。函数先处理空输入，之后初始化长度、父下标和最佳结尾；父下标的缺失标记是 a.size()。

任意以 i 结尾的非单元素答案，都有倒数第二个下标 j；枚举这些 j，再接上 a[i]，覆盖所有可能。答案是全部 length[i] 的最大值，不能只读最后一格。例如 [1,2,3,0] 的答案是 3，而最后一格长度只有 1。

O(n log n)：相同长度只保留最小结尾

对于相同长度，结尾越小，后面越容易接上新值。因此维护 tails[k]：已处理前缀里，长度为 k+1 的严格递增子序列能够取得的最小结尾值。

对新值 x，找第一个不小于 x 的位置 p。若找到，用 x 替换该结尾；若不存在，在末尾增加一格。tails 本身严格递增，可以用二分查找寻找这个分界。

为什么替换不会损失最优长度？长度 p+1 原本有一个不小于 x 的结尾，换成更小的 x 只会扩大未来能接上的值域。另一方面，p 前一格严格小于 x，所以确实存在长度 p 的序列可以接上 x；被写入的新代表有实际序列支持。

严格递增使用 std::lower_bound。若改为允许相等值的不下降序列，应使用第一个大于 x 的位置，也就是 std::upper_bound；对 [2,2,2]，前者答案 1，后者答案 3。这不是可以忽略的实现细节，而是题目定义的变化。

tails 不是可直接输出的答案

输入 [3,5,6,2,4] 后，最终 tails=[2,4,6]。但原输入里 6 出现在 2、4 之前，[2,4,6] 并不是它的子序列。每格代表的是不同长度的最佳结尾，这些代表可能来自不同历史。

lis_binary 另外维护每格结尾所在的原下标 tail_index，以及每个原元素接到谁后面的 parent。在替换 p 格之前，先让当前元素的父下标指向当时 p−1 格的结尾；最后从最长格的结尾沿父链回溯。

父链总是指向更早的下标，且父值严格更小，所以恢复结果同时满足下标顺序与值顺序。不同平局处理可能恢复不同 LIS，两种实现只要求长度一致、各自方案合法。

平方实现时间 O(n²)、空间 O(n)；二分实现时间 O(n log n)、空间 O(n)，包含恢复所需的下标和父链。空输入返回空序列，全相等输入返回长度 1；负值不影响比较前提。源码将平方实现限制为 2000 个元素，二分实现限制为 100000 个元素。

四、最长公共子序列：二维状态与滚动覆盖

给定 A="ABC"、B="BAC"，寻找两者共有的最长子序列。答案长度是 2，"AC" 和 "BC" 都合法。它们不要求在原字符串中连续；这与最长公共子串是不同问题。

定义 dp[i][j] 为 A 的前 i 个字符、B 的前 j 个字符的 LCS 长度。任一前缀为空时答案为 0。

• 末字符相同：可以把这个公共字符接在两个更短前缀的 LCS 后，取 dp[i−1][j−1]+1。
• 末字符不同：它们不能同时作为同一个公共末字符，至少舍弃一方的末字符，取 max(dp[i−1][j],dp[i][j−1])。

末字符相同时，存在包含这一对末字符的最优解：若一个最优公共子序列没有用到双方末字符，可以接上这个字符而变得更长；若只用到了其中一方的末字符，可以把另一方对应的匹配位置移到其末尾。因此选对角线转移覆盖一个最优方案。

最后的 C 匹配，来自左上角 dp[2][2]=1，所以长度为 2。从右下角恢复时先拿 C，再遇到不匹配且上下候选平局，源码优先往上走，最后拿 A，逆序得到 "AC"。

一行数组中同时存在旧行与新行

每格只依赖上、左、左上三格。把列方向选择为较短字符串后，可以用 O(min(n,m)) 空间求长度；难点是左上角会被覆盖，需要临时变量保存它：

for (char x : *rows) {
    int diagonal = 0;
    for (std::size_t j = 1; j <= cols->size(); ++j) {
        const int above = dp[j];
        if (x == (*cols)[j - 1]) dp[j] = diagonal + 1;
        else dp[j] = std::max(dp[j], dp[j - 1]);
        diagonal = above;
    }
}

该片段来自 lcs_length。每次更新之前，dp[j] 是上一行的上方格；dp[j−1] 已变为当前行的左方格；diagonal 保存上一行的左上格。先备份 above，更新后再移交给 diagonal，三种角色才不会混淆。

错误实现可能直接写成“匹配时 dp[j]=dp[j−1]+1”。对 A="A"、B="AA"，第一列得到 1，第二列又用当前行的 1 加一，错误得到 2，相当于把 A 中同一个字符匹配了两次。正确答案只能是 1。

压缩掉的表不能直接回溯

只有最后一行长度时，中途每格选择往上还是往左的信息已经消失。不能从滚动数组直接执行前面的二维回溯。源码明确分为两个函数：lcs_length 求长度，lcs_restore 保留完整二维表并恢复一条 LCS。

滚动版时间 O(nm)、空间 O(min(n,m))；完整表恢复版时间和空间 O(nm)，另需 O(n+m) 以内的回溯步数。还存在使用分治和线性工作空间恢复 LCS 的方法，但需要额外推导，不能仅将完整表删掉就声称具备相同能力。

源码比较 std::string 的字节，文中案例使用 ASCII 字母。对 UTF-8 中文，直接按 char 比较会把一个汉字拆成多个字节；若要按字符求 LCS，应先按明确编码解码成码点序列，并明确是否还需要组合字符规范化。两个输入分别限制为 2000 字节，空字符串的长度是 0，恢复结果为空。

五、计数动态规划：循环交换会改变计数对象

硬币面值集合 [1,2]，每种可以无限使用，目标金额 3。此时先明确：“1+2”和“2+1”算一份，还是两份？

如果顺序无关，组合只有 {1,1,1} 与 {1,2}，共 2 份。若顺序有关，有序序列为 [1,1,1]、[1,2]、[2,1]，共 3 份。

组合：先确定允许的硬币种类

使用硬币种类作为外层循环。处理完某种面值后，dp[x] 只统计使用已处理种类凑出金额 x 的组合数；同种可用多次，所以金额正序。

dp[0] = 1;
for (int c : coins)
    for (int x = c; x <= amount; ++x)
        checked_add(dp[x], dp[x - c]);

初始数组 [1,0,0,0]。处理面值 1 后为 [1,1,1,1]；处理面值 2 时，金额 2 增加 dp[0]=1，金额 3 增加 dp[1]=1，结果 [1,1,2,2]。

每个组合按面值种类的固定处理顺序生成，不会因为交换硬币排列再计一次。dp[0]=1 表示唯一的空组合；若初始化为 0，就没有任何起点能贡献计数，全部状态永远是 0。

有序序列：枚举最后一枚硬币

金额作为外层循环，内层枚举最后一枚面值 c。每个较小金额的有序序列都可以接上 c，且最后一枚不同的类别不会重复：

dp[0] = 1;
for (int x = 1; x <= amount; ++x)
    for (int c : coins)
        if (c <= x) checked_add(dp[x], dp[x - c]);

金额 1 有 [1]，所以计数为 1；金额 2 有 [1,1]、[2]，计数为 2；金额 3 的最后一枚若是 1，可以接在金额 2 的两份方案后，若是 2，可以接在金额 1 的一份方案后，合计 3。

两段循环都像“dp[x]+=dp[x−c]”，但前者的隐含状态包括已允许的种类，后者的状态包括任意面值构成的全部有序前缀。仅看一行加法无法判断它们统计的是哪个问题。

重复面值、不可达与整数增长

源码先排序、去重面值，因此 [1,1,2] 与 [1,2] 表示同一个硬币种类集合。若输入两个 1 其实代表有身份的不同物品，就不能套用这种去重语义；那是另一个计数问题。

面值必须为正：它保证前驱金额更小，并避免出现可以任意插入零面值硬币的无限序列。无硬币、金额 0 有一份空方案；无硬币、金额大于 0 则计数为 0。

面值种类数 k、目标 A：两种算法时间 O(kA)、空间 O(A)，以固定宽度整数运算计；若换为任意精度整数，还要计入随结果位数增加的加法成本。源码将目标限制为 1000、输入面值数限制为 50，并不因此保证 64 位计数一定足够。

checked_add 在加法前检查 b > max−a，超出 uint64_t 范围就抛出异常。[1,2] 的有序计数随目标增长，金额 100 已超出该范围；代码用这个案例验证溢出路径，避免悄悄回绕为小数。若问题要求对某个模数取余，应明确改成模计数；那时输出语义也相应改变。

六、让状态与恢复方案一起接受独立校验

配套程序中的校验不依靠重新抄一份相同递推：

LIS 校验覆盖元素取自 {-1,0,1}、长度 0 到 8 的全部 9841 个输入；LCS 校验覆盖字母表 {A,B}、长度 0 到 5 的全部 3969 对字符串。背包以固定随机种子生成小输入并枚举，计数覆盖面值 1 到 5 的全部子集、目标 0 到 12。

这些校验能检验空输入、重复值、不可达、循环方向和恢复合法性，但有限枚举不能代替对任意输入的正确性证明。前面每节的状态定义、前驱覆盖与依赖顺序说明了为什么递推可推广；测试负责尽早发现实现与证明不一致的地方。

更多前置内容可以接着看序列算法中的前缀和与窗口；图与最短路则把“先算依赖，再求当前状态”放到有向图和路径问题中。动态规划的填表顺序也可以看作在无环依赖图上求值。

本篇关于子问题、前驱选择与父指针的建模方式可对照 MIT 6.006 的动态规划、LCS 与父指针讲义；背包与伪多项式时间可对照 MIT 6.006 背包专题讲义。本文的手算输入、实现限制和枚举校验与下载源码对应。