动态规划的状态设计
动态规划把重复子问题的答案保存下来，并按依赖顺序组合成更大问题。解题重点是定义足以决定后续选择的状态，而不是先写一张 dp 数组。
1. 什么时候考虑动态规划
常见信号：
- 问题要求最优值、方案数或可达性。
- 大问题可以由更小规模的同类问题组成。
- 递归搜索反复遇到相同参数组合。
- 当前选择的影响能由有限状态概括。
如果每一步存在明确的局部最优交换证明，贪心可能更简单；如果子问题几乎不重复，记忆化的收益有限；需要列出所有方案时，回溯仍要访问对应输出空间。
2. 状态必须包含决定未来的信息
设计状态时完成一句话：
dp[i][s]表示处理到位置 i，处于状态 s 时的什么最优值或方案数。
例如股票问题中，只记录第 i 天最大利润不够，因为是否持有股票会影响下一天能做的动作。可以定义：
cash[i] = 第 i 天结束时不持有股票的最大利润
hold[i] = 第 i 天结束时持有股票的最大利润
状态应尽量小，但不能丢失影响未来的条件。把整条历史路径都塞进状态通常又失去动态规划的压缩价值。
3. 从最后一步推导转移
对每个状态问：到达这里的最后一个动作是什么？
cash[i] = max(cash[i - 1], hold[i - 1] + price[i])
hold[i] = max(hold[i - 1], cash[i - 1] - price[i])
第一式表示今天不持有：昨天也不持有，或昨天持有并在今天卖出。第二式表示今天持有：昨天已经持有，或今天买入。
转移需要覆盖所有合法来源，并且不同来源组合不会引入非法状态。若题目限制交易次数、冷冻期或手续费，就要把对应信息加入状态或转移。
4. 初始化定义了空问题语义
边界不只是代码补丁。它说明状态在最小输入下的含义：
long cash = 0;
long hold = Long.MIN_VALUE / 4;
不可达状态需要安全的负无穷。直接使用 Long.MIN_VALUE 后再加价格可能溢出，因此留出运算余量，或在转移前显式判断可达性。
网格路径需要初始化第一行、第一列，或在外侧加哨兵；背包需要区分“最多容量”与“恰好容量”的初值；计数问题还要明确空方案是否计为 1。
5. 计算顺序来自依赖关系
如果 dp[i] 依赖 dp[i - 1]，按 i 递增。二维网格依赖上方和左侧，按行列从小到大。
0/1 背包的一维压缩需要容量倒序：
for (Item item : items) {
for (int capacity = limit; capacity >= item.weight(); capacity--) {
dp[capacity] = Math.max(
dp[capacity],
dp[capacity - item.weight()] + item.value()
);
}
}
倒序保证本轮每个物品只使用一次。完全背包允许重复使用同一物品，通常容量正序。循环方向是状态版本依赖的一部分，不能作为记忆口诀脱离语义。
6. 自顶向下与自底向上
6.1 记忆化搜索
从原始问题递归，只计算实际到达的状态，容易从暴力搜索改造。需要处理递归深度、缓存键和“未计算”哨兵。
6.2 表格递推
按依赖顺序迭代，避免调用栈，通常更容易压缩空间。即使最终使用表格，也可以先写递归关系验证状态是否完整。
两种方式的渐进复杂度都等于状态数量乘以每个状态的转移数量，前提是每个状态只求一次。
7. 空间压缩前先确认旧状态何时失效
如果当前行只依赖上一行，可以用两个数组；如果每个位置只依赖旧的两个标量，可以滚动变量。
long previousCash = cash;
cash = Math.max(cash, hold + price);
hold = Math.max(hold, previousCash - price);
先保存 previousCash，避免更新后的 cash 被同一天的 hold 转移错误使用。
空间压缩会降低可读性，也可能无法还原具体方案。面试时先给出清晰二维状态，再说明压缩条件，通常比直接写难以解释的一维代码更可靠。
8. 怎样证明转移完整
- 状态覆盖：每个合法解在某个终态中表示。
- 来源完整：到达当前状态的最后一步只可能来自列出的前置状态。
- 来源合法：每个转移不会违反题目约束。
- 无后效性：状态保存的信息足以决定未来，不需要知道被丢弃的历史。
- 计算有序：使用状态前，它已经按同一版本语义计算完成。
如果无法完成这五点，先修状态定义，不要继续补 if。
9. 常见问题
9.1 动态规划与贪心有什么区别
动态规划保留多个状态并比较所有合法来源；贪心每一步只保留一个局部选择，需要证明被丢弃方案永远不可能更优。能写出 dp 不代表贪心不成立，反之亦然。
9.2 为什么状态越多不一定越安全
冗余维度会增加时间、空间和转移错误，还可能保存实际不影响未来的历史。状态只需包含区分未来合法选择和结果所需的信息。
9.3 怎样恢复具体选择方案
保存每个状态来自哪个前驱，或从最终 dp 值逆向判断哪个转移成立。空间压缩可能覆盖这些信息，需要单独保存决策或重新计算。
9.4 DP 数值为什么容易溢出
方案数、路径和收益会快速增长。根据上界选择 long、BigInteger 或按题意取模；不可达哨兵参与加法时也要防止溢出。
10. 面试题
10.1 编辑距离的状态和转移怎样定义
出现公司：字节跳动
考察重点
- 前缀状态怎样隔离历史。
- 插入、删除、替换对应哪些前驱。
- 空字符串边界与空间压缩。
相关内容：第 2 节“状态必须包含决定未来的信息”至第 5 节“计算顺序来自依赖关系”。
参考回答
定义 dp[i][j] 为第一个字符串前 i 个字符变成第二个字符串前 j 个字符的最少操作数。末尾字符相同则来自 dp[i-1][j-1]；不同则在删除 dp[i-1][j]、插入 dp[i][j-1]、替换 dp[i-1][j-1] 中取最小再加 1。
边界是空串变成长度 j 的前缀需要 j 次插入，长度 i 的前缀变空需要 i 次删除。时间 O(mn)，空间 O(mn)，只依赖上一行和当前行左侧时可压缩到 O(n)。
10.2 最长公共子序列怎样设计状态，为什么不是子串问题
出现公司：美团
考察重点
- 子序列允许跳过字符，子串要求连续。
- 两个前缀状态与最后字符选择。
- 转移为什么覆盖所有合法解。
相关内容：第 2 节“状态必须包含决定未来的信息”、第 3 节“从最后一步推导转移”、第 8 节“怎样证明转移完整”。
参考回答
定义 dp[i][j] 为两个字符串前 i、前 j 个字符的最长公共子序列长度。末尾字符相同，可以接在更短前缀的公共子序列后，得到 dp[i-1][j-1]+1；不同则至少跳过一个末尾字符，取 dp[i-1][j] 与 dp[i][j-1] 最大值。
子序列允许删除中间字符，因此状态只看前缀，不要求当前匹配段连续；最长公共子串需要记录“以当前位置结尾的连续长度”，状态和答案更新方式不同。