动态规划解决的是「子问题被反复求解」的浪费：把每个状态的答案存下来，后面直接查表，让指数级递归降回多项式时间。它的难点从不在代码长短，而在于状态定义必须精确到足以支撑后续所有决策。

它解决什么问题

很多最优化与计数问题都能拆成结构相同的子问题：爬 n 级台阶的方法数，取决于 n-1 级和 n-2 级；凑出金额 j 的最少硬币数，取决于 j 减去每种硬币面额之后的结果。直接对这类问题做朴素递归，同一个状态会被展开成天文数字次的重复调用——斐波那契递归树里 f(n-2) 出现两次、f(n-3) 出现三次，节点数随 n 指数膨胀。动态规划的核心动作只有一个：给每个状态分配一个格子，算过一次就存起来，从此以空间换时间，每个状态只求解一次。

核心原理

三个适用条件

一个问题能用动态规划，需要同时满足三点：

  1. 最优子结构：原问题的最优解由子问题的最优解组合而成。比如最短路径中，A 到 C 的最短路若经过 B，那么其中 A 到 B 那一段必然也是最短的。
  2. 重叠子问题：不同分支会反复碰到同一个子问题，缓存才有价值。如果子问题彼此独立（如归并排序），那是分治，不是 DP。
  3. 无后效性：一个状态的值确定之后，只与状态本身有关，与「怎么到达这个状态」无关。这保证了转移时不需要携带历史路径。

五步法

写任何一道 DP 题，都按固定顺序走一遍：

  1. 定义状态：用一句完整的话说明 dp[i]（或 dp[i][j]）代表什么，以及最终答案落在哪个格子上。
  2. 写转移方程：问自己「最后一步发生了什么」，当前状态由哪几个更小的状态推出来。
  3. 初始化：没有前置状态时的边界值。求最值时常用 0 或一个不可能的大数来表达「不可达」。
  4. 确定遍历顺序：保证计算当前状态时，它依赖的旧状态已经全部算好。
  5. 核对返回值：答案不一定是 dp[n]，也可能是整表的最大值（如最长递增子序列）。

五步里第一步最关键：状态含义一旦含糊，后面四步都是在碰运气。

深入机制

从记忆化搜索到递推

DP 有两种等价写法。记忆化搜索是自顶向下：保留递归结构，只加一张缓存表，命中就直接返回：

int[] memo;

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

递推是自底向上：明确遍历顺序，从最小状态一路填表到目标：

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

两者的渐近复杂度相同。记忆化的好处是只访问真正可达的状态、不用事先想清楚遍历顺序，适合状态关系复杂的题（如区间 DP、树形 DP）；递推没有递归栈开销，还便于做空间压缩——上例中每个状态只依赖前两个，整张表被压成两个变量。压缩的前提是确认旧值之后不会再被读取。

背包问题族：倒序遍历到底防的是什么

01 背包：每件物品只能取一次，求容量限制下的最大价值。二维状态 dp[i][j] 表示「只考虑前 i 件物品、容量为 j 时的最大价值」，转移分「不取」与「取」第 i 件两种情况。压缩成一维后：

int knapsack(int[] w, int[] v, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < w.length; i++) {
        for (int j = capacity; j >= w[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[capacity];
}

容量循环必须倒序，这是 01 背包最经典的考点。原因在于 dp[j - w[i]] 必须是「还没考虑第 i 件物品」时的旧值；如果正序遍历，j - w[i] 比 j 小、已经在本轮被第 i 件物品更新过，再拿它做转移，等于同一件物品被放进了两次。倒序时 j - w[i] 尚未被本轮触碰，读到的一定是上一轮的残留，恰好满足「每件只能用一次」的语义。

对照之下，完全背包（物品无限取）容量要正序：恰恰需要利用本轮已更新的 dp[j - w[i]]，让当前物品反复参与转移。遍历方向不是代码风格问题，而是在控制「同一物品能否重复使用」。另外求方案数时，问组合数通常外层遍历物品，问排列数通常外层遍历容量——循环顺序不同，计数语义完全不同。

序列问题：把状态锚定在「结尾」上

股票与子序列是面试中最高频的两类序列 DP，共同技巧是把状态绑定在具体位置上：

  • 最长递增子序列：dp[i] 定义为以 nums[i] 结尾的最长递增子序列长度，而不是「前 i 个元素里的答案」。这样转移时只需向前找比 nums[i] 小的位置取最大值再加一，最终答案是全表最大值。若定义成「前 i 个」，遇到新元素时无法判断它能否接在已知子序列之后。
  • 最长公共子序列：dp[i][j] 表示两个字符串前 i、前 j 个字符的 LCS 长度，按末尾字符是否相等分两种情形转移。
  • 股票买卖（以含冷冻期为例）：把「第 i 天结束时的局面」拆成持股、处于冷冻期、空仓可买三个互斥子状态，每个子状态只从明确的来源转移。整个股票系列的精髓就是状态机拆分，而不是拿一个 dp[i] 硬套。

工程实践

  • 想不清遍历顺序就先写记忆化：递归结构天然保证依赖先于使用被算好，写对之后再改递推，比一上来就填表稳得多。
  • 初始化要表达语义：dp[0] = 0 通常是「空集的答案」；求最少次数时其余位置设成不可能的大值表示不可达，结束时检查目标格是否仍是大值来决定是否返回 -1。
  • 空间压缩前先画依赖图：确认当前行只依赖上一行或前几个值，再启用滚动数组；背包一维化的遍历方向写错，答案会悄无声息地偏大。
  • 小样本手推整张表：用 n=3 级别的输入手算每格 dp 值，与代码输出逐格对照，能抓出九成的初始化与顺序错误。

对比与权衡

维度 动态规划 贪心 回溯
适用信号 重叠子问题 + 最优子结构 局部最优可扩展成全局最优 需要枚举全部方案
决策方式 汇总子问题的最优结果 每步直接锁定当前最优 试错，失败即撤销
时间复杂度 状态数 × 转移代价，多项式 通常 O(n log n)，排序主导 指数级，靠剪枝控制
典型题型 背包、子序列、路径计数 区间调度、跳跃游戏 排列、组合、N 皇后

贪心可以看作 DP 的特例：当每个状态只需保留一个最优分支就足够时，整张 DP 表退化成几个变量。回溯则是 DP 的前身：当子问题互不重叠、或题目要求输出所有方案时，只能枚举。

面试视角

怎么判断一道题能不能用 DP？ 先问两个问题：能否拆成同构的小问题？小问题是否被反复求解？两个都成立，再验证无后效性——状态的答案与到达路径无关。三点齐备，DP 才成立。

记忆化搜索和递推选哪个？ 渐近复杂度相同。状态关系复杂、遍历顺序不明显时先写记忆化，只算可达状态；顺序清晰、需要压缩空间或担心栈深时改递推。

01 背包一维化后容量为什么倒序？ 因为 dp[j - w[i]] 必须读「尚未放入第 i 件」的旧值。正序会让它先被本轮更新，等价于同一件物品被重复装入，语义悄悄变成完全背包。

求方案数和求最值，初始化有什么区别？ 方案数中 dp[0] 通常为 1（空方案也算一种），其余为 0；求最值时 dp[0] 多为 0，不可达状态要用无穷大或 -1 单独标记，避免「没算过」的格子被当成合法答案参与取 max。

小结

  • DP 的三块基石：最优子结构、重叠子问题、无后效性，缺一不可。
  • 五步法里状态定义是纲：先用一句完整的中文说清 dp[i] 的含义，再谈转移。
  • 记忆化与递推等价，前者自然后者高效；空间压缩以「旧值不再被读」为前提。
  • 01 背包倒序、完全背包正序，本质是控制同一物品能否重复参与转移。
  • 序列问题把状态锚定在「以 i 结尾」，是最常见也最实用的设计手法。