动态规划
动态规划把较小子问题的答案保存下来，后面遇到同一子问题时直接复用，不再重复计算。“状态”记录定义一个子问题所需的信息，“递推关系”说明怎样用其他状态的答案求出当前答案。本页讨论的递推中，状态依赖不能绕回尚未算完的自身，因此构成有向无环图。记忆化是在递归需要某个答案时计算并缓存它；制表法则事先安排计算顺序，先算依赖项。设计时最重要的是弄清楚：状态需要记住什么，递推又为什么没有遗漏合法选择。
设计检查清单
- 状态（State）： 最少需要保留哪些信息，才能让剩余问题独立于到达当前状态的路径？
- 值（Value）：
dp[state]具体代表什么？是可行性、方案数、最小成本、最大价值，还是具体的解（Witness）？ - 转移（Transition）： 哪些更小的状态可以推导出当前状态？
- 边界（Base Cases）： 最小的有效子问题是什么？
- 顺序（Order）： 在读取某个依赖项之前，它是否已经计算完成？
- 答案（Answer）： 最终结果存储在哪个状态，或需要通过哪个聚合操作得出？
自顶向下 vs 自底向上
复杂度估算： 状态总数 单次转移的工作量。
空间压缩原则： 仅当被覆盖的状态在后续转移或答案重建中不再被需要时，才可安全压缩内存。
正确性证明模式
- 状态充分性： 证明状态定义涵盖了所有影响结果的历史信息。
- 归纳法： 基于依赖顺序进行归纳。假设较小状态的值是正确的，证明递推关系考察了所有合法的最终选择，并依据目标函数正确地进行选择或组合。
何时不该使用动态规划
以下情况 DP 可能不是最优解：
- 状态依赖无界历史： 所选状态仍依赖无法压缩的长历史。
- 状态空间过大： 状态空间比直接搜索（如回溯）还大。
- 贪心/交换性质适用： 存在贪心策略或交换论证，无需比较多个备选方案。
注：扩展状态维度有时能恢复正确性，但可能导致算法在工程上不可行。
状态设计示例：最少硬币
面额为 [1,3,4] 的正整数硬币可无限使用。优先拿大面额会把 6 凑成 4+1+1，需要三枚；3+3 只要两枚。反例推翻了这条贪心规则，但“有重叠子问题”本身还不能证明新递推正确。
定义 dp[t] 为恰好凑出 t 所需的最少硬币数。设 dp[0]=0，无法凑出的金额初始化为无穷大，不能设零。对正数 t，枚举不超过 t 的面额 c，取 1+dp[t-c] 的最小值。每个解都有最后一枚硬币，移走它后恰好留下相应较小金额，因此没有遗漏选择。正面额保证依赖严格变小。金额 0 到 6 的结果为 [0,1,2,1,1,2,2]。目标 T、面额数 k 时，时间 O(Tk)、空间 O(T)。若只有面额 [4]，目标 6 就不可达。
def min_coins(coins, target):
if target < 0 or any(c <= 0 for c in coins):
raise ValueError("positive denominations and nonnegative target required")
dp = [0] + [float("inf")] * target
for amount in range(1, target + 1):
for coin in coins:
if coin <= amount:
dp[amount] = min(dp[amount], 1 + dp[amount - coin])
return dp[target]
assert min_coins([1, 3, 4], 6) == 2
assert min_coins([4], 6) == float("inf")
assert min_coins([], 0) == 0
不同问题需要记住什么
斐波那契数列只需一个下标及可复用的先前结果。0/1 背包还要记住物品是否可用与剩余容量，最长公共子序列用两个前缀长度描述状态。最短路径中的动态规划解释什么图顺序能让距离依赖无环。这些例子的差别在于状态必须保留什么信息，而不在于有没有一张表。