动态规划

动态规划（Dynamic Programming，DP）是算法世界里最具张力、也最容易让人"卡壳"的一个主题。它的代码往往只有寥寥数行，思想却能在陌生题目面前把人挡在门外；它的理论门槛看似只是一句"分治 + 记忆化"，但能否在第一时间构造出正确的状态定义，几乎直接决定了"会做"与"不会做"。本文将以 DP 的三要素为主线，从最朴素的斐波那契讲起，一路推进到背包家族、区间 DP、树形 DP 与状态压缩，并讨论记忆化与递推的取舍，力图把"为什么这样设计状态"的直觉讲透。文中例题全部取自 LeetCode 并附题号，每读完一节即可上手刷对应题目。

为什么需要动态规划：动机与起源

先看一个最朴素的问题（LeetCode 509「斐波那契数」）：求第 $n$ 个斐波那契数。最容易想到的写法是直接照搬递推式：

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

这段代码在 $n=40$ 时就已经明显感觉到延迟，$n=50$ 几乎无法接受。原因在于它做了海量的重复计算：fib(5) 会调用 fib(4) 与 fib(3)，而 fib(4) 又会再次调用 fib(3) 与 fib(2)，于是 fib(3) 被算了两次，越往下重复越严重，整体时间复杂度退化为 $O(2^n)$。

如果我们把每个 fib(k) 的结果第一次算出来时记到一张表里，后续再遇到就直接查表，复杂度立刻降到 $O(n)$。这就是动态规划最核心的动机：用空间换时间，消除重叠子问题的重复计算。

但 DP 真正的威力远不止于"加个记忆化"。它是一种建模方式：把一个复杂的最优化或计数问题，分解成若干个规模更小的子问题，并保证子问题的解能够组合出原问题的解。一旦你能写出正确的"状态"和"转移"，剩下的就只是工程实现。

需要强调的是，DP 不是贪心，也不是普通的分治：

• 贪心要求每一步的局部最优能导向全局最优，这需要问题具有"贪心选择性质"，并非所有问题都满足。
• 分治把问题切成互不相交的子问题分别求解；DP 则面向重叠的子问题——子问题之间共享更小的子问题，反复求解会浪费。
• DP 还额外要求最优子结构：原问题的最优解可以由子问题的最优解构造出来。

理解这三者的边界，是判断一道题该用哪种方法的第一步。

核心思想与正确性直觉

动态规划的正确性建筑在两个性质之上，缺一不可。

最优子结构

如果一个问题的最优解，可以由其子问题的最优解组合而成，就称该问题具有最优子结构。以 0/1 背包（后文的 LeetCode 416）为例：在前 $i$ 个物品、容量 $j$ 下的最优解，要么不选第 $i$ 个物品（子问题：前 $i-1$ 个、容量 $j$），要么选（子问题：前 $i-1$ 个、容量 $j - w_i$）。两种情况都依赖于"子问题的最优解"，于是最优子结构成立。

反例是"最长简单路径"：从 $u$ 到 $v$ 的最长简单路径并不能由某个中间节点 $k$ 的最长路径拼接而成，因为拼接后可能产生环、违反"简单"约束。这类问题没有最优子结构，通常不能用 DP 直接求解。

重叠子问题

子问题被反复求解，是 DP 有意义的另一个前提。斐波那契是最典型的例子；LCS（LeetCode 1143）中 dp[i][j] 也会被 dp[i+1][j] 与 dp[i][j+1] 同时依赖。如果一个问题的子问题树是"树形"的（互不重叠），那么用普通分治就够了，不需要 DP。

无后效性

这是状态设计时最容易踩坑的一条约束：“现在怎么走到这里"不影响"未来能怎么走”，只取决于"现在在哪里"。换句话说，状态必须完整地刻画"从现在起所有可能决策的后果"，过去的细节不能在暗中影响未来。

以 LeetCode 64「最小路径和」为例：求网格从左上到右下、数字和最小的路径。如果用"当前走了哪些格子"作为状态，那状态数会爆炸，而且带有强烈后效性；但如果状态只取"当前坐标 $(i, j)$"，因为每一步只往右、往下走，过去的路径形状不影响从 $(i, j)$ 出发的最优决策，无后效性成立，DP 就能工作。

无后效性常常是状态设计成败的关键：当你发现某个状态似乎"漏了什么信息"导致转移写不出来，往往就是需要把那个信息补进状态维度里；反之，如果状态维度太多导致爆炸，就要思考能否用某种性质把维度压缩掉。

DP 三要素：状态、转移、边界

把任何一道 DP 题拆开，最终都要回答三个问题。

状态定义

“dp 数组的含义是什么” 是 DP 建模中最关键的一步，往往也是题目的难点。一个好的状态定义应当满足：

1. 完备性：原问题的答案能从某个（或某些）状态推出。
2. 可转移性：每个状态都能由"更小"的状态计算得到，且计算顺序是清晰的（通常构成 DAG）。
3. 无后效性：如上节所述。
4. 规模可控：状态总数在时间、空间预算之内。

状态定义的"维度"直接决定复杂度。一维状态 $O(n)$、二维状态 $O(n^2)$ 是最常见的；当问题带额外约束（如"恰好选 $k$ 个"“容量恰好为 $W$”）时，往往要把约束升级为状态的一维。

状态转移方程

转移方程描述"如何从已知状态推出新状态"。它本质上是对"最后一步决策"的枚举：考虑到达当前状态的最后一种选择是什么，枚举所有可能，取最优（最优化问题）或求和（计数问题）。

写转移方程时，一个反复有用的思路是：“我从哪里来” 或 “我到哪里去”。

• “我从哪里来”：对于状态 dp[i]，枚举它的前驱 dp[j]（$j < i$），用前驱更新自己。LIS、背包都是这种写法。
• “我到哪里去”：对于状态 dp[i]，枚举它能转移到的后继 dp[k]，用自己更新后继。图上 DP 常用。

两种视角等价，选哪种取决于哪种枚举更自然。

边界条件与初始化

边界条件是 DP 的"地基"。常见的初始化模式有：

• 空集是合法的：如 0/1 背包中 dp[i][0] = true（什么都不选即可凑出和 0）。
• 非法状态设为 $-\infty$ 或 $0$：计数问题中，不可达状态贡献为 0；最优化问题中，不可达状态设为 $-\infty$ 防止被错误转移。
• 起点为 1：如不同路径（LeetCode 62）中 dp[0][0] = 1。

边界写错是 DP 题最常见的 bug 来源之一。一个有效的检查手段是：对每个转移，确认它引用的所有前驱状态都已被正确初始化，特别是"恰好"“至多”"至少"这类约束下的非法状态。

两种实现范式：自顶向下与自底向上

DP 有两种等价的实现方式，理解它们的差异对工程实践很重要。

自顶向下（记忆化搜索）

从原问题出发，递归地求解子问题，遇到已经算过的子问题直接返回缓存。本质是"带缓存的递归"。

#include <vector>

// 自顶向下：记忆化搜索
int fibMemo(int n, std::vector<int>& memo) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

int fib(int n) {
  std::vector<int> memo(n + 1, -1);
  return fibMemo(n, memo);
}

它的优点是只计算真正需要的状态，对状态空间稀疏的问题（如值域很大但实际可达状态少）非常友好；代码结构贴近自然递推式，思考负担小。缺点是递归调用栈有深度限制，常数因子也略大。

自底向上（递推）

从最小子问题开始，按某种拓扑顺序逐个填表，直到原问题。

#include <vector>

int fib(int n) {
  if (n <= 1) return n;
  std::vector<int> dp(n + 1, 0);
  dp[0] = 0; dp[1] = 1;
  for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

自底向上没有递归栈开销，常数小，且天然适合做空间优化（滚动数组）。缺点是必须自己想清楚计算顺序，确保填某个状态时它依赖的状态都已就绪；对稀疏状态空间也会"白白"计算一些用不到的状态。

如何选择

维度	自顶向下	自底向上
思考方式	贴近递推式，自然	需要规划填表顺序
状态稀疏性	只算需要的状态	可能多算无用状态
空间优化	较难做滚动	容易做滚动
栈深度	受递归深度限制	无栈问题
常数	较大（函数调用）	较小

经验上：先写记忆化搜索保证正确，再视情况改写为递推做优化。在状态依赖关系复杂（如某些图上 DP、数位 DP）时，记忆化搜索的代码量明显更短、更不易错。

斐波那契：DP 的最小工作集

回到开篇的斐波那契（LeetCode 509）。把它套进 DP 三要素的框架：

• 状态：dp[i] 表示第 $i$ 个斐波那契数。
• 转移：dp[i] = dp[i-1] + dp[i-2]。
• 边界：dp[0] = 0, dp[1] = 1。

注意一个空间优化的细节：转移只依赖前两项，所以根本不需要整个数组，两个变量就够了：

int fib(int n) {
  if (n <= 1) return n;
  int prev2 = 0, prev1 = 1;
  for (int i = 2; i <= n; i++) {
    int cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

这种"只保留固定前驱"的优化思路在 DP 中极为常见，后文的背包空间优化也是同一思想。斐波那契本身简单，但它把 DP 的所有要素都浓缩在了一起：状态定义、转移方程、边界、空间优化、两种实现范式。理解了它，就理解了 DP 的骨架。同构的 LeetCode 70「爬楼梯」（每步爬 1 或 2 阶，求爬到第 $n$ 阶的方案数）共享完全相同的递推结构，是第一道练手题的最佳选择。

0/1 背包：分割等和子集（LeetCode 416）

问题描述

LeetCode 416：给定只含正整数的数组 nums，判断能否把它分割成两个元素和相等的子集。例如 [1,5,11,5] 可以分为 [1,5,5] 与 [11]，返回 true。

转化：设总和为 $S$，若 $S$ 为奇数直接返回 false；否则问题等价于"从数组中选出若干数（每个最多一次），恰好凑出 $S/2$"。这正是 0/1 背包的可行性版本：每个物品"选或不选"，问容量 $W = S/2$ 能否恰好装满。

状态与转移

• 状态：dp[i][j] 表示前 $i$ 个数中能否选出若干个数，使和恰好为 $j$。
• 转移：对第 $i$ 个数，分"不选"和"选"两种决策。
  • 不选：dp[i][j] = dp[i-1][j]。
  • 选（仅当 $nums[i-1] \le j$）：dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]]。
• 边界：dp[i][0] = true（什么都不选即可凑出 0）。

这里的关键直觉是：枚举"最后一个决策"——对第 $i$ 个数的最后一步决策只有两种（选或不选），分别对应两个子问题，取"或"。

#include <vector>

class Solution {
public:
  bool canPartition(std::vector<int>& nums) {
    int sum = 0;
    for (int x : nums) sum += x;
    if (sum % 2) return false;
    int target = sum / 2, n = nums.size();

    // dp[i][j]：前 i 个数能否凑出和 j
    std::vector<std::vector<bool>> dp(
        n + 1, std::vector<bool>(target + 1, false));
    for (int i = 0; i <= n; i++) dp[i][0] = true;

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= target; j++) {
        dp[i][j] = dp[i - 1][j];            // 不选
        if (j >= nums[i - 1]) {             // 选
          dp[i][j] = dp[i][j]
                  || dp[i - 1][j - nums[i - 1]];
        }
      }
    }
    return dp[n][target];
  }
};

复杂度：时间 $O(nS)$，空间 $O(nS)$。注意 $S$ 是数值大小而非输入规模，所以 0/1 背包是伪多项式时间算法——这正是它能被用于子集和等 NP 问题的近似求解，但也意味着 $S$ 很大时它并不"快"。

空间优化：滚动数组

观察转移：dp[i][*] 只依赖 dp[i-1][*]，更早的行不再需要。于是可以把第一维压掉，只剩一个长度 $W+1$ 的一维数组。但这里有个陷阱：如果正序遍历 $j$，更新 dp[j] 时用到的 dp[j-nums[i]] 已经是"本层"更新过的值，相当于第 $i$ 个数被选了多次，退化成完全背包。

正确做法是倒序遍历，保证 dp[j-nums[i]] 仍然是"上一层"的旧值：

#include <vector>

class Solution {
public:
  bool canPartition(std::vector<int>& nums) {
    int sum = 0;
    for (int x : nums) sum += x;
    if (sum % 2) return false;
    int target = sum / 2;

    std::vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int x : nums) {
      // 倒序遍历，保证每个数只被用一次
      for (int j = target; j >= x; j--) {
        dp[j] = dp[j] || dp[j - x];
      }
    }
    return dp[target];
  }
};

复杂度：时间 $O(nS)$，空间 $O(S)$。这种"倒序保证每物品只用一次、正序允许重复使用"的差别，是理解整个背包家族的钥匙。

方案回溯

LeetCode 只要求判断可行性；若要进一步输出具体的分割方案，需保留完整二维 dp 表，从 dp[n][target] 倒推：若 dp[i][j] 为真而 dp[i-1][j] 为假，说明 nums[i-1] 必选，回退到 dp[i-1][j-nums[i-1]]；否则未选，回退到 dp[i-1][j]。这样能在 $O(n)$ 时间内还原一个子集。

同模型题目

• LeetCode 1049「最后一块石头的重量 II」：两两粉碎等价于把石头分成两堆使重量差最小，与 416 同一模型。
• LeetCode 494「目标和」：给每个数赋 $\pm$ 号使总和为 target，求方案数——把 || 换成 += 的计数版 0/1 背包。

背包家族：完全背包与变种

背包问题是 DP 最庞大的一个分支。理解了 0/1 背包，其余变种大多是"调整转移规则"——以下例题全部来自 LeetCode。

完全背包：零钱兑换（LeetCode 322）

每种物品可以选无限次。LeetCode 322：给定硬币面额 coins 与金额 amount，求凑出 amount 的最少硬币数，无解返回 $-1$。例如 coins = [1,2,5]、amount = 11，答案为 $3$（$5+5+1$）。

• 状态：dp[j] 表示凑出金额 $j$ 的最少硬币数。
• 转移：dp[j] = min(dp[j], dp[j-c] + 1)，对每枚硬币 $c$。
• 边界：dp[0] = 0，其余为 $+\infty$（不可达）。

只需把 416 空间优化版中的倒序遍历改成正序即可：

#include <vector>
#include <algorithm>

class Solution {
public:
  int coinChange(std::vector<int>& coins, int amount) {
    const int INF = amount + 1;  // 足够大的"无穷"
    std::vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int c : coins) {
      // 正序遍历：同一硬币可被多次使用
      for (int j = c; j <= amount; j++) {
        dp[j] = std::min(dp[j], dp[j - c] + 1);
      }
    }
    return dp[amount] > amount ? -1 : dp[amount];
  }
};

直觉解释：正序遍历时，dp[j-c] 在本层可能已经"用过"硬币 $c$，于是 dp[j] 就能在此基础上再用一次，等价于无限次选取。INF 取 amount + 1 即可（最多用 amount 枚面额 1 的硬币），同时避免 +1 时整数溢出。

方案数背包：零钱兑换 II（LeetCode 518）

把 min 换成 +=，即求"恰好凑出 amount 的方案数"：dp[0] = 1，转移 dp[j] += dp[j-c]。

这里有一个 LeetCode 高频陷阱——循环顺序决定计数语义：

• 外层物品、内层容量（上面的写法）：每种面额按顺序被考虑，得到的是组合数——{1,2} 与 {2,1} 算同一种方案，LC 518 要的就是这个。
• 外层容量、内层物品：不同顺序被分别计数，得到的是排列数——LC 377「组合总和 Ⅳ」要求的正是这个。

同一个状态定义，仅交换两层循环，语义就从"组合"变成"排列"。写之前务必想清楚题目要哪一种。

二维费用背包：一和零（LeetCode 474）

LC 474：给定二进制字符串数组 strs 与两个上限 $m$、$n$，问最多能选出多少个字符串，使选中字符串中 0 的总数不超过 $m$、1 的总数不超过 $n$。每个字符串有两种"费用"，状态升级为二维 dp[j0][j1]，两个容量维都倒序：

#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
  int findMaxForm(std::vector<std::string>& strs,
                  int m, int n) {
    std::vector<std::vector<int>> dp(
        m + 1, std::vector<int>(n + 1, 0));
    for (auto& s : strs) {
      int c0 = 0, c1 = 0;
      for (char ch : s) (ch == '0' ? c0 : c1)++;
      // 两个容量维度都要倒序
      for (int j = m; j >= c0; j--)
        for (int k = n; k >= c1; k--)
          dp[j][k] = std::max(
              dp[j][k], dp[j - c0][k - c1] + 1);
    }
    return dp[m][n];
  }
};

多重背包与竞赛向变种

多重背包（每种物品有数量上限 $c_i$）在 LeetCode 没有直接对应题，但在竞赛中常见：把 $c_i$ 二进制拆分为 $1, 2, 4, \dots, 2^k, r$（$r$ 为余数），拆出的 $O(\log c_i)$ 个"打包物品"做 0/1 背包即可，整体复杂度 $O(nW \sum \log c_i)$；进一步还可用单调队列优化到 $O(nW)$。此外还有分组背包（每组最多选一个，转移时多一层组内枚举）、依赖背包（选 $A$ 必须先选 $B$，转树形 DP）等。这些变种的思想高度统一：状态还是"前 $i$ 个物品 + 容量 $j$"，区别只在于"第 $i$ 个物品能怎么选"导致的转移形式不同。

最长公共子序列 Longest Common Subsequence（LeetCode 1143）

问题描述

LC 1143：给定两个字符串 $A$、$B$，求它们的最长公共子序列长度（子序列不要求连续）。

状态与转移

• 状态：dp[i][j] 表示 $A$ 的前 $i$ 个字符与 $B$ 的前 $j$ 个字符的 LCS 长度。
• 转移：看 $A[i-1]$ 与 $B[j-1]$ 是否相等。
  • 相等：dp[i][j] = dp[i-1][j-1] + 1（这两个字符配对，加到前面的 LCS 上）。
  • 不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（至少有一个字符不参与配对）。
• 边界：dp[0][*] = dp[*][0] = 0。

#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
  int longestCommonSubsequence(std::string text1,
                               std::string text2) {
    int m = text1.size(), n = text2.size();
    std::vector<std::vector<int>> dp(
        m + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (text1[i - 1] == text2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = std::max(dp[i - 1][j],
                              dp[i][j - 1]);
        }
      }
    }
    return dp[m][n];
  }
};

复杂度 $O(mn)$，空间 $O(mn)$。空间优化上，由于 dp[i][j] 依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]，可以滚动到两行 $O(\min(m,n))$，但需要额外变量保存左上角的旧值。

与编辑距离的关系

LCS 的转移是编辑距离（LeetCode 72）的一个特例。编辑距离允许插入、删除、替换三种操作，转移为：

若 A[i]==B[j]: dp[i][j] = dp[i-1][j-1]
否则: dp[i][j] = 1 + min(dp[i-1][j-1],  // 替换
                         dp[i-1][j],    // 删除 A[i]
                         dp[i][j-1])    // 插入 B[j]

只保留"删除"一种操作时（LeetCode 583「两个字符串的删除操作」），最少删除次数恰为 $|A| + |B| - 2 \cdot LCS$。LCS 与编辑距离共享同一族状态定义，理解了其中一个，另一个几乎是免费赠送。

输出具体 LCS

与背包类似，从 dp[m][n] 回溯：若 A[i-1]==B[j-1] 且 dp[i][j]==dp[i-1][j-1]+1，则该字符属于 LCS，向左上走；否则向较大方向走。LeetCode 1092「最短公共超序列」要求的正是这类方案还原。

最长递增子序列 Longest Increasing Subsequence（LeetCode 300）

问题描述

LC 300：给定序列 $a_1, a_2, \dots, a_n$，求其最长的严格递增子序列长度（子序列不要求连续）。

$O(n^2)$ 解法

• 状态：dp[i] 表示以 $a_i$ 结尾的 LIS 长度。
• 转移：dp[i] = max(dp[j] + 1)，其中 $j < i$ 且 $a_j < a_i$。
• 边界：dp[i] = 1（每个元素自身构成长度为 1 的子序列）。

#include <vector>
#include <algorithm>

class Solution {
public:
  int lengthOfLIS(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
          dp[i] = std::max(dp[i], dp[j] + 1);
        }
      }
      maxLen = std::max(maxLen, dp[i]);
    }
    return maxLen;
  }
};

注意状态定义为"以 $a_i$ 结尾"而非"前 $i$ 个元素的 LIS"——前者能保证转移时新元素能合法接在后面，后者则无法在 $O(1)$ 内判断能否拼接。这种"以某处结尾/开头"的技巧在子序列 DP 中极其常见。

$O(n \log n)$ 解法：耐心排序

$O(n^2)$ 在 $n=10^5$ 时不可接受。一个巧妙的优化是维护一个数组 tails，其中 tails[k] 表示"所有长度为 $k+1$ 的递增子序列中，最小的结尾元素"。tails 始终保持严格递增，于是对新元素 $x$ 可以二分：

• 若 $x$ 大于 tails 末尾，说明能接在最长子序列后，直接 push_back，LIS 长度 +1。
• 否则，找到第一个 $\ge x$ 的位置替换之（让同等长度的子序列结尾更小，为未来留出更大接续空间）。

#include <vector>
#include <algorithm>

class Solution {
public:
  int lengthOfLIS(std::vector<int>& nums) {
    std::vector<int> tails;
    for (int num : nums) {
      auto it = std::lower_bound(tails.begin(),
                                 tails.end(), num);
      if (it == tails.end()) {
        tails.push_back(num);
      } else {
        *it = num;
      }
    }
    return tails.size();
  }
};

注意：tails 数组并不是一个真实的 LIS，只是其长度等于 LIS 长度。若要还原具体方案，需要在每次二分时记录每个元素对应的"前驱指针"，最后从 tails 末尾对应的元素回溯。

若要求非严格递增（允许相等），把 lower_bound 换成 upper_bound 即可。这种"换一个二分函数"的小调整是 LIS 题目里最常见的陷阱。

相关问题

• LIS 方案数（LeetCode 673「最长递增子序列的个数」）：在 $O(n^2)$ 转移中同步维护"以 $a_i$ 结尾、长度为 $dp[i]$ 的方案数"即可。
• 二维 LIS（LeetCode 354「俄罗斯套娃信封」）：先按宽度升序、同宽时高度降序排序，再对高度求严格 LIS——降序正是为了挡住同宽信封互相套入。
• 最长公共递增子序列（LCIS）：LCS 与 LIS 的结合，竞赛常见，LeetCode 无直接对应题。

最大子数组和 Maximum Subarray（LeetCode 53，Kadane 算法）

问题描述

LC 53：给定数组 $a_1, a_2, \dots, a_n$（元素可正可负），求其连续子数组的最大和。例如 $[-2,1,-3,4,-1,2,1,-5,4]$ 的最大子段为 $[4,-1,2,1]$，和为 $6$。

这是"以 $i$ 结尾"状态定义的又一经典实例，与 LIS 同族，但转移更简单——无需回看所有 $j<i$，只看 $i-1$ 即可。

状态与转移

• 状态：dp[i] 表示以 $a_i$ 结尾的最大子数组和。
• 转移：dp[i] = max(nums[i], dp[i-1] + nums[i])。
  • 要么单独成段（取 $a_i$ 自身），要么接在以 $a_{i-1}$ 结尾的最大子段之后。
  • 当 dp[i-1] < 0 时，接上去只会拖累和，转移自然退化为 nums[i]。
• 边界：dp[0] = nums[0]。
• 答案：dp[0..n-1] 中的最大值，因为最优子段不一定以末尾结尾。

#include <vector>
#include <algorithm>

class Solution {
public:
  int maxSubArray(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n);
    dp[0] = nums[0];
    int ans = dp[0];
    for (int i = 1; i < n; i++) {
      dp[i] = std::max(nums[i], dp[i - 1] + nums[i]);
      ans = std::max(ans, dp[i]);
    }
    return ans;
  }
};

空间优化：滚动变量

dp[i] 只依赖 dp[i-1]，连滚动数组都用不上，一个变量即可承载"上一层"：

#include <vector>
#include <algorithm>

class Solution {
public:
  int maxSubArray(std::vector<int>& nums) {
    int cur = nums[0];  // 相当于 dp[i-1]
    int ans = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
      cur = std::max(nums[i], cur + nums[i]);
      ans = std::max(ans, cur);
    }
    return ans;
  }
};

复杂度：时间 $O(n)$，空间 $O(1)$。这已是最优——至少要把每个元素看一遍。

为什么是 DP 而非贪心

Kadane 算法常被误读为贪心（“前缀和变负就丢弃”），但它的骨架是标准 DP：定义状态、写出转移、再做滚动优化。所谓"丢弃负前缀"，本质是 max(nums[i], dp[i-1]+nums[i]) 在 dp[i-1] < 0 时取 nums[i] 的自然推论。先有状态转移方程，才谈得上贪心的直觉解释；因果不可倒置。

变种与延伸

• 最小子数组和：把 max 换成 min，同样一遍扫描。
• 环状数组最大子段（LeetCode 918）：分两情况取较大者——普通最大子段（Kadane），或总和减去最小子段（跨过首尾）。
• 最大子数组乘积（LeetCode 152）：负数会翻转符号，需同时维护"以 $i$ 结尾的最大值与最小值"两个状态。
• 分治解法：$T(n)=2T(n/2)+O(n)$，合并时跨中点的最大子段 = 左半从右端延伸的最大值 + 右半从左端延伸的最大值。该结构可封装进线段树，支持单点修改后动态查询区间最大子段和。
• 二维最大子矩阵：枚举行的上下边界，对列做一维 Kadane，复杂度 $O(n^3)$，LeetCode 无直接对应题。

区间 DP

当问题可以描述为"对一个序列/区间做某种合并或划分操作"时，往往用区间 DP。

通用模板

状态 dp[i][j] 表示处理子区间 $[i, j]$ 的最优解。转移时枚举分割点 $k$，把区间拆成两段（是否共享端点因题而异）：

dp[i][j] = min/max over k of { dp[i][k] + dp[k+1][j] + cost }

其中 cost 是合并两部分的代价。计算顺序按区间长度从小到大，保证计算长区间时它包含的所有短区间都已就绪。

以 LeetCode 1039「多边形三角剖分的最低得分」为例：凸多边形每个顶点有权值，把它三角剖分，每个三角形的得分为三顶点权值之积，求总得分最小值。固定边 $(i, j)$ 并枚举第三个顶点 $k$——"最后加入的三角形"把多边形分成 $[i, k]$ 与 $[k, j]$ 两个子多边形：

#include <vector>
#include <climits>
#include <algorithm>

class Solution {
public:
  int minScoreTriangulation(std::vector<int>& values) {
    int n = values.size();
    // dp[i][j]：剖分子多边形 [i..j] 的最小得分
    std::vector<std::vector<int>> dp(
        n, std::vector<int>(n, 0));
    for (int len = 3; len <= n; len++) {      // 区间长度
      for (int i = 0; i + len - 1 < n; i++) { // 起点
        int j = i + len - 1;
        dp[i][j] = INT_MAX;
        for (int k = i + 1; k < j; k++) {     // 分割点
          dp[i][j] = std::min(dp[i][j],
              dp[i][k] + dp[k][j]
              + values[i] * values[j] * values[k]);
        }
      }
    }
    return dp[0][n - 1];
  }
};

复杂度 $O(n^3)$。区间 DP 的标志是"三重循环：长度、起点、分割点"。注意长度小于 3 的区间（一条边）无法构成三角形，得分天然为 0，正好充当边界。

枚举型区间 DP：为运算表达式设计优先级（LeetCode 241）

三角剖分是最优化区间 DP；把转移里的 min/max 换成"收集所有可能结果"，区间 DP 同样适用于枚举/计数问题。LC 241：给定含 +、-、* 的表达式，返回所有加括号方式可能得到的结果。以 2-1-1 为例：(2-1)-1 = 0、2-(1-1) = 2，答案为 [0, 2]。

与三角剖分的"最后一个三角形"同理，表达式的最终值由最后执行的运算符决定，它把区间一分为二。但这里子问题的解不是单个最优值，而是该子表达式的全部可能取值——左右两半的取值要两两组合：

• 状态：memo[l][r] 表示子表达式 $num[l..r]$ 能算出的所有值（一个列表）。
• 转移：枚举区间内运算符位置 $k$ 作为最后执行的运算符，左右两侧的取值做笛卡尔积，按运算符合并。
• 边界：单个操作数 memo[i][i] = {num[i]}。

用记忆化搜索写最自然——这正是"自顶向下"范式的主场：

#include <vector>
#include <string>

class Solution {
  std::vector<int> num;
  std::vector<char> op;
  // memo[l][r]：子表达式 num[l..r] 的全部取值
  std::vector<std::vector<std::vector<int>>> memo;

  std::vector<int> solve(int l, int r) {
    if (!memo[l][r].empty()) return memo[l][r];
    if (l == r) return memo[l][r] = {num[l]};
    std::vector<int> res;
    for (int k = l; k < r; k++) {  // 最后执行的运算符
      for (int a : solve(l, k))
        for (int b : solve(k + 1, r)) {
          if (op[k] == '+') res.push_back(a + b);
          else if (op[k] == '-') res.push_back(a - b);
          else res.push_back(a * b);
        }
    }
    return memo[l][r] = res;
  }

public:
  std::vector<int> diffWaysToCompute(std::string expr) {
    num.clear(); op.clear();  // 防止对象复用时残留
    for (size_t i = 0; i < expr.size(); ) {
      if (isdigit(expr[i])) {
        int v = 0;
        while (i < expr.size() && isdigit(expr[i]))
          v = v * 10 + (expr[i++] - '0');
        num.push_back(v);
      } else {
        op.push_back(expr[i++]);
      }
    }
    int m = num.size();
    memo.assign(m, std::vector<std::vector<int>>(m));
    return solve(0, m - 1);
  }
};

241 还能再进一步：只问"有多少种括号化方式使结果为某个值"，把取值列表改成 map<值, 方案数> 即可。布尔情形下取值只有真/假两种，连 map 都省了，退化为两个计数数组——这正是下一小节的题目。

计数型区间 DP：布尔运算（LeetCode 面试题 08.14）

面试题 08.14「布尔运算」：给定由操作数 0/1 与运算符 &、|、^ 组成的表达式 s 及目标值 result，求有多少种加括号方式使表达式求值为 result。以 1^0|0|1、目标值 $0$ 为例：1^((0|0)|1) 与 1^(0|(0|1)) 两种括号化都求值为 $0$，答案为 $2$。

与 241 的"最后一个运算符"同理，但子问题的解不是取值列表，而是为真/为假的方案数两个量——左右两半的真假组合共同决定结果，必须同时记录：

• 状态：dpT[i][j]、dpF[i][j] 分别表示子区间 $[i,j]$ 求值为真/假的方案数。
• 转移：枚举区间内的运算符位置 $k$（奇数下标）作为最后执行的运算符，按真值表把左右两半的真假组合累加进来。
• 边界：单个操作数 dpT[i][i] = (s[i]=='1')，dpF[i][i] = (s[i]=='0')。

#include <vector>
#include <string>

class Solution {
public:
  int countEval(std::string s, int result) {
    int n = s.size();
    if (n == 0) return 0;
    // dpT/dpF[i][j]：子区间 [i,j] 求值为 真/假 的方案数
    std::vector<std::vector<int>> dpT(
        n, std::vector<int>(n, 0));
    std::vector<std::vector<int>> dpF(
        n, std::vector<int>(n, 0));

    // 边界：单个操作数（偶数下标）
    for (int i = 0; i < n; i += 2) {
      dpT[i][i] = (s[i] == '1');
      dpF[i][i] = (s[i] == '0');
    }

    // 合法子表达式的长度为奇数：3, 5, 7, ...
    for (int len = 3; len <= n; len += 2) {
      for (int i = 0; i + len - 1 < n; i += 2) {
        int j = i + len - 1;
        // 枚举区间内的运算符（奇数下标）
        for (int k = i + 1; k < j; k += 2) {
          int lt = dpT[i][k-1], lf = dpF[i][k-1];
          int rt = dpT[k+1][j], rf = dpF[k+1][j];
          int total = (lt + lf) * (rt + rf);
          if (s[k] == '&') {
            dpT[i][j] += lt * rt;
            dpF[i][j] += total - lt * rt;
          } else if (s[k] == '|') {
            dpF[i][j] += lf * rf;
            dpT[i][j] += total - lf * rf;
          } else {  // '^'
            dpT[i][j] += lt * rf + lf * rt;
            dpF[i][j] += lt * rt + lf * rf;
          }
        }
      }
    }
    return result == 1 ? dpT[0][n - 1] : dpF[0][n - 1];
  }
};

一个简化技巧：对 & 与 |，先算出左右组合总数 (lt+lf)*(rt+rf)，再用"总数减去为真部分"得到为假部分（或反之），省去逐一枚举四种组合；^ 因真假对称分布，仍需显式写出两项。复杂度 $O(n^3)$，与 241、1039 同阶。

这道题点出了计数 DP 的一个通用范式：当子问题的结果是一组离散取值而非单一标量时，为每个取值各维护一个状态。后文树形 DP 的 dp[u][0/1] 同出此理。

博弈型 DP：石子游戏 II（LeetCode 1140）

LC 1140：若干堆石子排成一行，第 $i$ 堆有 $piles[i]$ 颗。Alice 先手，双方轮流行动：当前玩家可以拿走剩余石子堆中最前面的 $X$ 堆（$1 \le X \le 2M$），随后 $M$ 更新为 $\max(M, X)$；初始 $M=1$。双方都采取最优策略，求 Alice 最多能拿到的石子数。以 $[2,7,9,4,4]$ 为例：Alice 拿走第 1 堆（$2$ 颗），Bob 的最优应对是一次拿走接下来的两堆（$7+9$，此时 $M$ 升为 2），于是 Alice 可以收走最后两堆，共得 $2+8=10$ 颗。

这道题是博弈 DP 的入门经典，两个建模要点值得拆解：

• 零和结构省去一方状态：剩余石子总数固定为后缀和 $suf[i]$，当前玩家拿得越多，留给对手就越少，因此"当前玩家最优收益 = 剩余总量 − 对手最优收益"。无需同时记录两人得分，一个视角即可。
• 无后效性逼出的状态维度：只记录"从第几堆开始"是不够的——本轮能拿几堆取决于 $M$，而 $M$ 由过去的决策（上一轮拿了几堆）决定。不把 $M$ 纳入状态，未来决策就会暗中受过去影响，违反无后效性。这正是前文"状态漏了信息就补维度"判断法则的直接应用。

三要素如下：

• 状态：dp[i][m] 表示从第 $i$ 堆开始、参数为 $m$ 时，当前行动的玩家最多能拿到的石子数。注意状态与"先后手身份"解耦——无论轮到谁，子问题结构完全相同，这是零和博弈 DP 的标准技巧。
• 转移：枚举本轮拿走的堆数 $X$（$1 \le X \le 2m$ 且不越界）：dp[i][m] = max(suf[i] - dp[i+x][max(m,x)])。拿走前 $x$ 堆后，剩余 $suf[i+x]$ 颗由对手支配，对手在其子问题中最优拿走 dp[i+x][max(m,x)]，所以自己最终共拿 $suf[i] - dp[i+x][\dots]$。
• 边界：dp[n][m] = 0（无石子可拿）。
• 答案：dp[0][1]。

状态依赖天然指向"更靠后的后缀"——dp[i][m] 只读取 $i+x > i$ 的状态，因此两种实现范式都适用，下面各给一份。

方案一：自顶向下（记忆化搜索）

从 dfs(0, 1) 出发递归求解，转移式原样照抄，只计算实际可达的状态：

#include <vector>
#include <algorithm>

class Solution {
  int n;
  std::vector<int> suf;
  // memo[i][m]：从第 i 堆开始、参数为 m 时，
  // 当前行动的玩家最多能拿到的石子数
  std::vector<std::vector<int>> memo;

  int dfs(int i, int m) {
    if (i >= n) return 0;              // 边界：无石子可拿
    if (memo[i][m] != -1) return memo[i][m];
    int best = 0;
    // 枚举本轮拿走前 x 堆；剩余 suf[i+x] 颗由对手支配，
    // 对手在其子问题中最优拿 dfs(i+x, max(m,x))，
    // 故自己共拿 suf[i] - 对手最优收益
    for (int x = 1; x <= 2 * m && i + x <= n; x++) {
      best = std::max(best,
          suf[i] - dfs(i + x, std::max(m, x)));
    }
    return memo[i][m] = best;
  }

public:
  int stoneGameII(std::vector<int>& piles) {
    n = piles.size();
    // suf[i]：第 i 堆到末尾的石子总数（后缀和）
    suf.assign(n + 1, 0);
    for (int i = n - 1; i >= 0; i--)
      suf[i] = suf[i + 1] + piles[i];
    // m 只需开到 n：2m >= n - i 时已能拿完剩余全部
    memo.assign(n + 1, std::vector<int>(n + 1, -1));
    return dfs(0, 1);
  }
};

方案二：自底向上（递推）

按 $i$ 从后往前填表。注意这里多了一个显式的剪枝分支：$2M \ge n-i$ 时能一次拿完剩余全部，直接取后缀和：

#include <vector>
#include <algorithm>

class Solution {
public:
  int stoneGameII(std::vector<int>& piles) {
    int n = piles.size();
    // suffix[i]：第 i 堆到末尾的石子总数（后缀和）
    std::vector<int> suffix(n + 1, 0);
    for (int i = n - 1; i >= 0; --i)
      suffix[i] = suffix[i + 1] + piles[i];

    // dp[i][M]：从第 i 堆开始、参数为 M 时，
    // 当前行动的玩家最多能拿到的石子数
    std::vector<std::vector<int>> dp(
        n + 1, std::vector<int>(n + 1, 0));

    // 转移只依赖 i+x > i 的行，故 i 倒序填表；
    // M 的遍历方向不影响正确性（依赖全在后面的行）
    for (int i = n - 1; i >= 0; --i) {
      for (int M = n; M >= 1; --M) {
        // 能一次拿完剩余全部（X 可取到 n-i 堆），直接全拿
        if (i + 2 * M >= n) {
          dp[i][M] = suffix[i];
          continue;
        }
        // 枚举本轮拿走前 x 堆；拿完后对手面对子问题
        // dp[i+x][max(M,x)]，剩余石子由对手支配，
        // 故自己共拿 suffix[i] - 对手最优收益
        for (int x = 1; x <= 2 * M && i + x <= n; ++x)
          dp[i][M] = std::max(
              dp[i][M],
              suffix[i] - dp[i + x][std::max(M, x)]);
      }
    }
    return dp[0][1];
  }
};

两种方案的比对：

维度	记忆化搜索	自底向上递推
思考方式	转移式照抄，自然	需规划 $i$ 倒序的填表方向
实际计算量	只算从 $(0,1)$ 可达的状态	算满全部 $O(n^2)$ 个状态
边界处理	i >= n 递归出口，隐式	i + 2M >= n 剪枝分支，显式
常数开销	递归调用 + 缓存查询	纯循环，更 cache 友好
空间优化余地	难（依赖散在多个后继行）	同样难，但至少无递归栈

复杂度层面两者同阶：状态数 $O(n^2)$（M 只需开到 n，因为 $2M \ge n-i$ 时即可拿完剩余，无需更大的 M），每状态枚举 $O(n)$ 个 $x$，总时间 $O(n^3)$、空间 $O(n^2)$，对 $n \le 100$ 绰绰有余。差异在常数与工程细节：记忆化的"懒计算"会跳过不可达的 $(i, m)$ 组合，实际算的状态更少；递推没有递归栈开销，且 i + 2M >= n 分支把"能拿完就全拿"这一显然最优决策做成了 $O(1)$ 剪枝。本题数据范围小，任选其一即可；这种"记忆化先行定正确性、递推殿后优常数"的双写习惯，正是前文「记忆化与递推的取舍」一节推荐的工作流。

与 877 的对比点出了子问题形态的差异：877 中双方从两端取石子，子问题是真区间 $[i, j]$；而 1140 总是从剩余堆的最左端连续拿取，区间右端恒为 $n-1$，子问题退化为后缀，于是省掉一维、代价是把 $M$ 补进来。博弈类 DP 的状态设计，大多遵循同一条路线——先想"什么信息决定未来的可行动作"，再把这些信息一个不落地塞进状态。

经典应用

• 戳气球（LeetCode 312）：反向思考——把"最后戳的气球"作为分割点，是区间 DP 的经典反向建模。
• 切棍子的最小成本（LeetCode 1547）：与矩阵链乘法同构，cost 为当前棍子长度。
• 合并石头的最低成本（LeetCode 1000）：每次必须合并 $K$ 堆相邻石子，需要额外状态维度，是区间 DP 的 Hard 进阶。
• 分割回文串 II（LeetCode 132）：先 $O(n^2)$ 预处理回文判断，再做线性 DP 求最少切割数。
• 石子游戏（LeetCode 877）：博弈型区间 DP，dp[i][j] 记录先手的净胜分数。其进阶版 1140 已在上节展开。

区间 DP 的关键直觉是：最终的一次决策（最后加入的三角形、最后戳的气球、最后执行的运算符）把区间一分为二，两半互不相干地各自最优。这种"最后一次决策"的视角在最优化 DP 中反复出现。

树形 DP

当问题在一棵树上求解时，状态往往以"以节点 $u$ 为根的子树"为单位。

打家劫舍 III（LeetCode 337）

LC 337：房屋排成一棵二叉树，每个节点存有金额；直接相连的父子两家不能同时偷，求能偷到的最大金额。这正是经典题"没有上司的舞会"。

• 状态：dp[u][0/1] 表示以 $u$ 为根的子树中，$u$ 不偷/偷时的最大金额。
• 转移：
  • dp[u][1] = w[u] + dp[l][0] + dp[r][0]（$u$ 偷了，两个孩子都不能偷）。
  • dp[u][0] = max(dp[l][0], dp[l][1]) + max(dp[r][0], dp[r][1])（$u$ 不偷，孩子偷不偷都行，各自取较大）。
• 边界：空节点两种情形都为 0。

#include <array>
#include <algorithm>

class Solution {
  // 返回 {u 不偷, u 偷} 两种情形下子树的最大金额
  std::array<int, 2> dfs(TreeNode* u) {
    if (!u) return {0, 0};
    auto l = dfs(u->left);
    auto r = dfs(u->right);
    return {
      std::max(l[0], l[1]) + std::max(r[0], r[1]),
      u->val + l[0] + r[0]
    };
  }

public:
  int rob(TreeNode* root) {
    auto res = dfs(root);
    return std::max(res[0], res[1]);
  }
};

后序遍历天然保证子树先算完、再合并到父节点；让递归函数直接返回 dp[u][0/1] 两个状态，连外部的 dp 数组都省了。

二叉树的直径（LeetCode 543）

LC 543：求二叉树中任意两节点间最长路径的边数。对每个节点维护"向下延伸的最长链"，则经过该节点的最长路径 = 左右两条最长链之和，用一个全局变量更新答案即可：

#include <algorithm>

class Solution {
  int ans = 0;

  // 以 u 为端点向下延伸的最长链（边数）
  int dfs(TreeNode* u) {
    if (!u) return 0;
    int l = dfs(u->left);
    int r = dfs(u->right);
    ans = std::max(ans, l + r);  // 经过 u 的最长路径
    return std::max(l, r) + 1;
  }

public:
  int diameterOfBinaryTree(TreeNode* root) {
    dfs(root);
    return ans;
  }
};

同一套路的进阶题：LeetCode 124「二叉树中的最大路径和」（节点带权值，链和要"丢弃负值"，与 Kadane 同思想）、LeetCode 1245「树的直径」（多叉树，需维护前两条最长子链，会员题）。

树形背包

把"树"和"背包"结合：在树上选若干节点、满足父子依赖关系、总代价不超过 $W$ 的最大价值。状态 dp[u][j] 表示在 $u$ 的子树中选代价为 $j$ 的最优解，转移时把每个子树当作一个"物品组"做分组背包。复杂度分析上有"树形背包 $O(nW)$"的著名结论（用 size 合并技巧）。LeetCode 没有直接对应题，是竞赛常见专题。

树形 DP 的共同特征是：后序遍历保证子树先算完，再合并到父节点。状态维度通常带一个"以 $u$ 为根的子树"的隐含维度，外加一两个 0/1 或大小约束。

状态压缩 DP（状压 DP）

当状态中包含"一个集合是否包含某元素"这种二值信息，且集合规模较小（通常 $\le 20$）时，可以用一个整数的二进制位表示整个集合，这就是状态压缩 DP。

访问所有节点的最短路径（LeetCode 847）

旅行商问题（TSP）是状压 DP 的名片，但 LeetCode 主站没有原始 TSP；结构最贴近的是 LC 847：给定无向图，求访问每个节点至少一次的最短路径长度——可以从任意节点出发、在任意节点结束，允许重复经过。

• 状态：dp[S][v] 表示已访问节点集合为 $S$、当前位于 $v$ 时的最短路径长度。
• 转移：dp[S | (1<<u)][u] = min(dp[S][v] + dist[v][u])，其中 $u \notin S$。
• 边界：dp[1<<v][v] = 0（可以从任意节点出发）。
• 答案：$\min_v dp[(1<<n)-1][v]$（无需回到起点）。

由于允许重复经过，先用 Floyd 把原图"压缩"成任意两点间最短距离的完全图，之后每次"走到一个未访问节点"都取最短路：把最优行走中"首次访问新节点"的时刻抽出来，相邻两段的长度至少是对应的最短距离，故用最短距离做转移既不高估也不低估。

#include <vector>
#include <algorithm>

class Solution {
public:
  int shortestPathLength(
      std::vector<std::vector<int>>& graph) {
    int n = graph.size();
    const int INF = 1e9;

    // Floyd 预处理任意两点最短距离
    std::vector<std::vector<int>> dist(
        n, std::vector<int>(n, INF));
    for (int v = 0; v < n; v++) {
      dist[v][v] = 0;
      for (int u : graph[v]) dist[v][u] = 1;
    }
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          dist[i][j] = std::min(dist[i][j],
              dist[i][k] + dist[k][j]);

    // dp[S][v]：已访问集合为 S、当前位于 v
    int full = (1 << n) - 1;
    std::vector<std::vector<int>> dp(
        1 << n, std::vector<int>(n, INF));
    for (int v = 0; v < n; v++) dp[1 << v][v] = 0;

    for (int S = 1; S <= full; S++) {
      for (int v = 0; v < n; v++) {
        if (dp[S][v] == INF) continue;
        for (int u = 0; u < n; u++) {
          if (S & (1 << u)) continue;   // u 已访问
          dp[S | (1 << u)][u] = std::min(
              dp[S | (1 << u)][u],
              dp[S][v] + dist[v][u]);
        }
      }
    }
    int ans = INF;
    for (int v = 0; v < n; v++)
      ans = std::min(ans, dp[full][v]);
    return ans;
  }
};

复杂度 $O(2^n \cdot n^2)$。这看起来可怕，但对 $n \le 20$ 完全可行——这正是状压 DP 的"甜区"：集合规模在 20 左右、需要记录"哪些元素已用"的问题。真·TSP（恰好访问一次且回到起点）在 LeetCode 上最近的对应是 943「最短超级串」：预处理字符串两两的重叠长度后，套同一个 dp[S][v] 模板，只是还要记录转移路径以还原答案字符串。

状压的常用技巧

• 位运算：S | (1<<i) 加入元素、S & ~(1<<i) 删除元素、S & (1<<i) 判断是否包含、__builtin_popcount(S) 数集合大小。
• 子集枚举：for (int T = S; T; T = (T-1) & S) 枚举 $S$ 的所有非空子集，复杂度 $O(3^n)$。
• 预处理合法性：很多状压题先预处理"哪些状态合法"（如棋盘上哪些摆放不冲突），再 DP 转移。

更多 LeetCode 状压题：1349「参加考试的最大学生数」（棋盘逐行状压）、1879「两个数组最小的异或值之和」（配对问题）、1125「最小的必要团队」（技能集合覆盖）。当一道题的 $n \le 20$ 且涉及"用没用过"的集合信息，几乎可以条件反射地想到状压。

记忆化与递推的取舍

前面提到两种范式的差异，这里展开讲讲工程实践中的取舍。

优先用记忆化搜索的场景：

1. 状态空间稀疏。例如某些图上 DP 只有部分状态可达，自底向上会算一堆没用的状态。
2. 转移依赖关系复杂、不易确定计算顺序。例如某些带"跳跃"的 DP、数位 DP 中带前导零与上界约束的转移，记忆化写起来更接近自然递推式。
3. 调试期。记忆化代码更短、更不易在"填表顺序"上出错，先用它对拍验证正确性，再改递推优化常数。

优先用自底向上的场景：

1. 需要空间优化（滚动数组、原地覆盖）。记忆化天然带递归栈，难以做滚动。
2. 递归深度过大（如 $n=10^6$ 的线性 DP），递归会爆栈。
3. 对常数敏感（竞赛中卡常）。递推的循环展开、cache 友好性都更好。
4. 状态依赖形成清晰的拓扑序（如区间 DP 按长度递增、DAG 按拓扑序）。

一个常被忽视的点：记忆化搜索的"懒计算"特性使它对状态空间的实际利用更精确。例如数位 DP 中，每一位的"是否贴上界""是否有前导零"四个分支只有少数真正可达，自底向上递推反而要处理所有组合。这也是数位 DP 几乎都用记忆化模板的原因——详见 数位 dp 专篇。

数位 dp 是动态规划中一个独立且庞大的子专题，专门处理"在 $[L, R]$ 范围内满足某种数位性质（如不含 4、各位数字之和为 $k$）的数的计数"。它的状态设计（当前位、是否贴上界、是否贴下界、是否有前导零）与转移方式自成一派，是面试与竞赛中的高频考点，数位 dp 专篇 对其模板与典型例题做了系统讲解。

横向对比

把本文涉及的几类 DP 放在一起对照：

类型	状态维度	典型复杂度	LeetCode 例题	标志特征
线性 DP	1~2 维	$O(n)$ / $O(n^2)$	53、300、1143	沿序列推进
背包 DP	物品 + 容量	$O(nW)$（伪多项式）	416、322、518、474	容量维是数值
区间 DP	左右端点	$O(n^3)$	241、312、1039、1140	枚举分割点，按长度递增
树形 DP	节点 + 0/1 或容量	$O(n)$ / $O(nW)$	337、543、124	后序遍历，子树合并
状压 DP	集合 + 当前位置	$O(2^n \cdot n^2)$	847、943、1349	集合规模 $\le 20$
数位 DP	位 + 标志位	位数 × 状态数	233、902	逐位决策，贴上界

记忆口诀：线性背包区间树，状压数位分两路。识别题目类型后，状态定义与转移的"模板"就大致确定了，剩下的功夫在边界与剪枝。

实战场景

竞赛

DP 是算法竞赛的"半壁江山"。Codeforces Div.2 的 C/D 题几乎必有 DP；NOI/ICPC 区域赛里，树形 DP、状压 DP、数位 DP 都是常考类型。一个常见的备赛策略是：先打通"背包 + 区间 + 树形 + 状压"四大模板，再针对数位、概率/期望 DP、插头 DP 等高阶专题逐个突破。LeetCode 周赛与面试中，线性 DP、背包、区间三类出现频率最高——本文各节的题号本身就是一份由浅入深的练习清单。

工程

在工程实践中，DP 的影子比比不及：

• 生物信息学：序列比对（LCS / 编辑距离的变体）是 BLAST 等工具的核心。
• 自然语言处理：分词、词性标注的维特比算法本质是 HMM 上的 DP。
• 运筹优化：资源分配、排程问题常建模为背包或区间 DP。
• 版本控制：git diff 的最小编辑脚本就是编辑距离 DP 的方案回溯。
• 强化学习：值迭代、策略迭代都是 DP 思想在马尔可夫决策过程上的体现，"贝尔曼方程"即是 DP 转移方程。

理解了 DP，你会发现它不只是"一种算法"，而是一种把复杂决策问题"分层拆解 + 组合子解"的思维方式，几乎在任何需要"在多步决策中求最优"的领域都会再次相遇。

常见陷阱与边界条件

1. 状态定义模糊：把"前 $i$ 个"与"以 $i$ 结尾"混用。LIS（LeetCode 300）必须用"以 $i$ 结尾"，否则转移时无法判断能否拼接。写状态定义时务必问自己：“这个状态是否完整描述了影响未来的所有信息？”

2. 初始化遗漏：尤其是"恰好""至少"约束下，非法状态必须设为 $-\infty$（最优化）或 $0$（计数），否则会被错误转移污染。一个检查技巧：对每个转移，逐项确认它引用的前驱都已被正确初始化。

3. 填表顺序错误：自底向上时必须保证依赖关系形成 DAG 且按拓扑序填表。区间 DP 按长度递增、树形 DP 后序遍历、背包倒序/正序的选择，都是这一原则的体现。

4. 滚动数组覆盖：压缩维度时，若引用了"本层"还未更新的旧值，需要额外变量暂存（如 LCS 滚动时左上角的旧值）。背包的倒序遍历正是为了避免覆盖。

5. 后效性未消除：当状态似乎"漏了信息"导致转移不封闭，往往是需要补维度。例如"飞行问题"中必须把"当前剩余油量"纳入状态，否则未来决策会受过去路径影响。

6. 整数溢出：计数类 DP 的答案常常指数级增长，要尽早用 long long 甚至高精度。最优化 DP 中代价之和也可能溢出 int。

7. 负数下标 / 越界：状态中带"差值""偏移"时（如将容量为负的子问题平移到非负区间），极易越界。建议给数组多开几个元素、用偏移量统一处理。

8. 混淆"子序列"与"子串"：子串要求连续（如 LeetCode 718「最长重复子数组」，dp[i][j] 必须以两串当前位置结尾），子序列不要求（如 LC 1143，允许跳过不匹配字符）。两者状态设计差异显著，混用是常见错误。

9. lower_bound vs upper_bound：LIS（LC 300）中求严格递增用 lower_bound，非严格递增用 upper_bound。搞反是常见 bug。

10. 状压的范围判断：$n=20$ 时 $2^n \approx 10^6$ 尚可，$n=25$ 时 $2^n \approx 3 \times 10^7$ 就接近上限。盲目状压会 TLE/MLE，要先估算状态规模。

小结

动态规划的核心，是把"在多步决策中求最优/计数"的问题，拆解为状态 + 转移 + 边界三件套。状态定义是建模的灵魂，决定了问题能否被正确刻画；转移方程是对"最后一步决策"的枚举，决定了子问题如何组合；边界条件是地基，错了就全盘皆输。

实现上，自顶向下的记忆化搜索贴近自然思维、适合稀疏状态与调试，自底向上的递推常数小、易做空间优化、适合大规模与卡常场景。两者等价，取舍看问题特征。

从斐波那契到背包、从 LCS 到 LIS、从区间 DP 到树形 DP 再到状压，每一类问题都有相对固定的状态模板，但真正的能力差异在于"看到陌生题能否第一时间想到正确的状态定义"。这种直觉只能靠刷题与归纳积累：每做一道 DP 题，不妨停下来追问一句——"这道题的状态为什么这样设计？换一种定义会怎样？“久而久之，DP 就会从"玄学"变成"反射”。

最后给学习者一张路线图：先吃透线性 DP（LeetCode 53、300、1143）与背包家族（416、322、518、474），再练区间 DP（1039、312、241、1140）与树形 DP（337、543、124），接着挑战状压 DP（847、943、1349）与数位 dp，最后进阶到概率/期望 DP、插头 DP 等高阶专题。每一步都要带着"状态为什么这样设计"的追问，而不是机械套模板。DP 的精髓，正在于这种"建模—验证—优化"的反复打磨之中。