动态规划
动态规划（DP）保存重复子问题的答案，再按依赖顺序组合成更大问题的答案。解题时，先定义一个状态究竟表示什么，再决定怎样存进 dp 数组。本文从股票问题入手，讲解状态、转移和初始化，再用字符串与背包问题说明计算顺序和空间压缩。
设计 DP 时，可以按这五个问题依次检查状态与转移：
- 哪些信息会影响后续选择，需要保存在状态中？
- 当前状态能由哪些合法操作得到？
- 空输入和不可达状态怎样初始化？
- 按什么顺序计算，才能读到需要的旧结果？
- 压缩空间后，怎样恢复具体方案？
1. 面试核心
先记住这几条，再读正文- 状态完整性。 DP 状态必须包含决定后续合法选择的全部信息。只有后续选择与目标值都相同的子问题，才能复用同一状态结果。
- 编辑距离。 编辑距离用两个字符串的前缀长度定义状态，末尾字符不同时比较插入、删除和替换的成本。卡 · 编辑距离
- 子序列与子串。 最长公共子序列允许跳过字符，而公共子串要求字符在原字符串中连续出现。卡 · 最长公共子序列
- 状态压缩。 背包 DP 压缩成一维数组后，0/1 背包按容量倒序更新，完全背包则按容量正序更新。卡 · 计算顺序
- 初始值与不可达状态。 计数 DP 若把空方案视为一种合法方案，就将对应初值设为 1，并用不同标记区分不可达状态与合法零值。
2. 适用信号
动态规划通过复用子问题结果减少重复计算。看到以下信号时，可以尝试用它建模：
- 问题要求最优值、方案数或可达性。
- 大问题能拆成规模更小的同类问题。
- 递归搜索反复遇到相同的参数组合，也就是重叠子问题。
- 当前选择对未来的影响能用有限的状态信息概括。
最优化问题还需要最优子结构，也就是原问题的最优解能由子问题的最优解组合得到。如果子问题几乎不重复，保存结果所能减少的计算就有限。
枚举全部方案时，仍需付出生成这些结果的成本，见回溯。
若局部选择经证明始终安全，可以用更简单的贪心方法。
3. 状态设计
状态设计要回答：哪些不同经历可以共用同一个子问题答案？可以先用一句话定义它：
dp[i][s]表示处理到位置 i、处于条件 s 时的最优值或方案数。
这句话需要写清处理范围、约束和结果含义。比如，股票问题只记录日期和最大利润会遗漏持仓情况。持股时可以卖出，未持股时才可以买入，所以两者的后续动作不同。
本文例子允许多次交易、至多持有一股，且无手续费或冷冻期：
cash[i] = 第 i 天结束时，未持股的最大利润
hold[i] = 第 i 天结束时，持有一股的最大利润
交易次数受限时，状态还需表达剩余次数。如果存在冷冻期，就要区分当前是否允许买入；如果存在手续费，则需要调整对应的买卖转移。状态只保留这些影响未来的条件，让不同历史可以合并到同一个子问题。
4. 状态转移
状态转移说明当前答案怎样由已有答案得到。推导时，可以从“到达当前状态的最后一个动作”入手，列出所有合法来源。股票例子的转移如下：
cash[i] = max(cash[i-1], hold[i-1] + price[i])
hold[i] = max(hold[i-1], cash[i-1] - price[i])
今天未持股，可以是昨天就未持股，也可以是昨天持股、今天卖出。取两种结果的最大值，就得到 cash。今天持股同样有两种来源：继续持有昨日的股票，或用昨日未持股的利润买入。
这样按最后一步分类，就能检查是否漏掉合法选择。每条转移还需符合题目规则，避免把互相冲突的动作组合起来。
4.1 编辑距离
编辑距离求一个字符串变成另一个字符串所需的最少操作数。这里允许插入、删除和替换，每次成本都为 1。
设 dp[i][j] 为 A 的前 i 个字符变成 B 的前 j 个字符的最少操作数。前缀就是从字符串开头截取的连续部分。两串需要使用同一种字符单位，转移比较的是两个前缀的末尾字符：
若 A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1]
否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
dp[0][j] = j，dp[i][0] = i
末尾相等时，保留这个字符即可，操作数来自左上角的更短前缀。末尾不同时，比较以下三种来源，取最小值再加一次操作：
- 删除 A 的末尾字符，来自
dp[i-1][j]。 - 在 A 的末尾插入 B 的末尾字符，来自
dp[i][j-1]。 - 将 A 的末尾字符替换成 B 的末尾字符，来自
dp[i-1][j-1]。
空串变成长度 j 的前缀，需要 j 次插入；长度 i 的前缀变成空串，需要 i 次删除。比如，cat 变成 cut 只需替换 a，距离为 1。
两串长度为 m、n 时，时间与二维空间都为 O(mn)。只求距离时，当前格只依赖上一行和当前行左侧，可保留前后两行，将空间降为 O(n)。
4.2 最长公共子序列
最长公共子序列允许跳过字符，但保留原来的先后顺序。设 dp[i][j] 为 A 的前 i 个字符与 B 的前 j 个字符的最长公共子序列长度：
若 A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp[0][j] = dp[i][0] = 0
两个末尾字符相等时，可以把它接到更短前缀的公共子序列后，长度加 1。不同时，公共子序列至少要跳过一个末尾字符，所以比较上方和左方，取较大值。任一前缀为空时，共同长度为 0。
比如，abc 与 ac 的结果为 2，因为跳过 b 后得到 ac。时间和二维空间都为 O(mn)，m、n 分别是两串长度。
最长公共子串要求连续，因此状态要记录以两个当前位置结尾的连续匹配长度。末尾不相等时，这段连续匹配就中断，状态归零。最长匹配可以在任意位置结束，所以答案取全表最大值。
5. 初始化
初始化定义最小问题的答案，后续转移才能有起点。初值要由状态含义推导，常见的边界情况如下：
- 计数问题若存在一个空方案，初值就是 1。
- 恰好装满背包时，只有容量 0 初始可达，其余容量先标记为不可达。
- 容量只要求不超过上限、收益非负时，可以用“不选物品”的收益 0 初始化。
- 网格路径要处理第一行、第一列的前驱边界，也可在表外加一圈辅助位置来统一转移。
不可达标记常被称为哨兵值，用来区分合法答案与尚无方案的状态。使用它之前应先判断可达性，再参与加减。比如，用 Long.MIN_VALUE 表示负无穷时，减去正数会下溢。加正数虽然未溢出，也会生成一个伪造的有限值，破坏不可达标记。
也可以在证明运算范围后，用 Long.MIN_VALUE / 4 这样的有限负值预留算术余量。但仍需保证它与合法收益区分，并让不可达转移保持无效。预留余量只解决数值范围问题。
股票例子可以直接按首日情况初始化：未持股利润为 0，持股利润为买入价的负值。这样就避开了哨兵运算：
static long maxProfit(int[] prices) {
if (prices.length == 0) return 0;
long cash = 0;
long hold = -(long) prices[0];
for (int i = 1; i < prices.length; i++) {
long previousCash = cash;
cash = Math.max(cash, hold + prices[i]);
hold = Math.max(hold, previousCash - prices[i]);
}
return cash;
}
输入价格要求非负。[3,1,4] 返回 3，对应在价格 1 时买入、价格 4 时卖出。空数组直接返回 0。每个交易日只更新两个状态，所以时间为 O(n)，辅助空间为 O(1)。
6. 计算顺序
计算顺序要保证：读取某个状态时，它已经算好，而且仍是所需的那一轮结果。若 dp[i] 依赖 dp[i-1]，就按 i 递增计算。二维网格依赖左方与上方时，也可以按行列递增。
0/1 背包规定每件物品最多用一次。压成一维数组后，转移需读取“尚未使用当前物品”的上一轮结果：
for (int i = 0; i < weights.length; i++) {
for (int c = limit; c >= weights[i]; c--) {
dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
}
}
这里 weights 为正整数，values 为非负收益。dp[c] 表示容量最多为 c 时的最大收益，初值为 0。容量倒序更新时，较小容量还未被当前物品更新。所以，从 dp[c-weights[i]] 转移时，当前物品只会被加入一次。
比如，只有重量 2、收益 3 的一件物品，容量为 4。倒序更新的答案为 3。正序会先写 dp[2]=3，再读取这个新值，得到 dp[4]=6，相当于重复使用了该物品。完全背包允许同一物品重复使用，才采用这种正序转移。循环方向由状态依赖决定，需要连同状态含义一起解释。
7. 自顶向下与自底向上
同一组状态和转移，可以用递归求值，也可以按顺序填表。两种方式的区别在于从哪些状态开始，以及怎样安排计算。
7.1 记忆化搜索
记忆化搜索从目标递归，只计算实际到达的状态，并保存结果供再次访问时复用。它容易从暴力搜索改造，但要同时考虑递归深度。
缓存键需包含完整状态，“未计算”标记也需区别于合法答案，具体见递归。
7.2 表格递推
表格递推按依赖顺序迭代填表，省去递归调用栈，也便于复用数组。即使最终使用表格，也可以先写递归关系，检查状态与来源是否完整。
两种方式在每个状态只求一次时，时间都等于全部转移工作的总和。若每条转移为 O(1)，可以用状态数乘每个状态的转移数估算。
8. 空间压缩
空间压缩通过覆盖已用完的结果，减少同时保留的状态。压缩前，先写清完整状态，再确认每个旧值最后在哪里使用。
当前行只依赖上一行时，可复用两行数组。如果只依赖几个标量，就可以用变量滚动更新。最长公共子序列（LCS）若压成一行，还需保存即将被覆盖的左上角旧值。背包则通过循环方向，保证读到所需的上一轮或本轮结果。
股票例子保存 previousCash，表示昨日未持股的利润。在本文无手续费、无冷冻期的模型中，改用新 cash 也会得到相同数值。因为当天先卖再买回，只会回到原来的持股利润。保留旧值则能让代码直接对应递推式，交易规则变化后也便于核对。
压缩会让状态的读取顺序更难辨认，也会覆盖恢复方案所需的前驱信息。若要返回具体选择，可以另存决策，或保留原表逆推；也可以按需重新计算。面试时应先解释清楚完整状态，再说明哪些结果已经用完、可以覆盖。
9. 转移完整性
转移式写出后，还要检查它是否覆盖所有合法方案。可以逐项核对以下五个条件：
- 状态覆盖：每个合法解都能由某个终态表达。
- 来源完整：到达当前状态的最后一步，都落在列出的转移中。
- 来源合法：每条转移都满足题目约束。
- 无后效性：状态保留的信息足以决定未来，省略的历史不再影响后续选择。
- 计算有序：前驱已经计算完成，读取的是转移要求的那一轮结果。
若其中一项无法解释，应回到状态定义和转移重新推导。小规模穷举还可以作为基准，检查转移是否遗漏或多算了方案。
10. 常见问题
下面补充状态数量、方案恢复与数值范围的判断，并说明 DP 和贪心的关系。
10.2 状态维度
状态维度只需区分会改变未来选择的条件。每多一个维度，都增加需要计算和存储的状态，也增加转移出错的机会。因此，应删去无关历史，但保留持仓、剩余资源等会改变后续动作的信息。
10.3 方案恢复
记录每个状态选中的前驱，即可从终态逆向恢复方案。也可以保留完整 dp 表，从最终值反推哪些转移成立。存在多个最优来源时，需要约定返回任意方案还是全部方案，再决定保留多少选择信息。
10.4 数值范围
方案数、路径和收益会随规模增长，所以需要按上界选择数值类型。超出 long 范围时，可用任意精度整数 BigInteger；题目规定计数取模时，则按要求保存余数。最优值比较需要保留数值的大小关系，直接取模会破坏这个关系。不可达哨兵也要先判断，再参与运算。
11 · 面试题卡片
11.1 编辑距离的状态和转移如何定义？
出现公司：字节跳动
考察重点：解释两个前缀怎样定义子问题，并推导三类操作的前驱、空串边界与空间压缩条件。
相关内容：编辑距离。
参考回答
定义 dp[i][j] 为 A 的前 i 个字符变成 B 的前 j 个字符的最少操作数。
末尾相等时，保留该字符，取 dp[i-1][j-1]。末尾不同时，比较以下三个前驱，取最小值再加 1：
- 删除来自
dp[i-1][j]。 - 插入来自
dp[i][j-1]。 - 替换来自
dp[i-1][j-1]。
空串变成长度 j 的前缀需 j 次插入，长度 i 的前缀变成空串需 i 次删除。时间与二维空间都为 O(mn)。只求距离时，可保留上一行和当前行，将空间压成 O(n)。
11.2 最长公共子序列的状态为何不同于子串？
出现公司：美团
考察重点：说明子序列为何能跳过字符，以及连续匹配要求怎样改变状态和答案的更新方式。
相关内容：最长公共子序列。
参考回答
子序列允许跳过字符，因此状态记录两个前缀的最优长度；子串要求连续，需要记录以当前位置结尾的匹配长度。
LCS 的末尾字符相等时，可以接在更短前缀的公共子序列后，得到 dp[i-1][j-1]+1。不同时，至少跳过一个末尾字符，所以取 dp[i-1][j] 与 dp[i][j-1] 的最大值。
子串遇到不匹配时，连续匹配就中断，状态归零。最长子串可以在任意位置结束，因此答案要取全表最大值。
11.3 0/1 背包压成一维后为何容量倒序？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：解释倒序怎样保留上一轮结果，并用反例说明正序为何会重复使用当前物品。
相关内容：计算顺序。
参考回答
容量倒序更新时，较小容量仍保存上一轮结果，所以当前物品只会被加入一次。
比如，一件物品重量 2、收益 3，背包容量 4，正确答案是 3。若正序更新，先得到 dp[2]=3，再读这个新值计算 dp[4]=6，同一物品就用了两次。完全背包允许重复使用，才使用这种正序转移。