核心思想
将原问题拆成重叠子问题，用表格保存子问题最优解，避免重复计算。
适用需同时满足：
- 最优子结构：全局最优可由子问题最优组合得到
- 无后效性：当前状态已包含做决策所需的全部历史信息
若只能证明「局部贪心」正确，用贪心；若子问题会重复出现且可合并，优先考虑 DP。
四步模板
- 定义状态：
dp[i]、dp[i][j]、dp[mask]等分别表示什么（尽量一维、语义清晰） - 初始条件：
dp[0]、空集、叶子节点等边界如何填 - 转移方程：枚举「最后一步 / 决策」从已知状态推到未知
- 答案：
max(dp[n])、dp[0][n-1]、所有终点状态的最值等
写代码前建议先画表格或 DAG，确认转移方向（从小到大 / 区间长度递增）。
线性 DP
最长上升子序列（LIS）
$O(n^2)$：dp[i] = 以 a[i] 结尾的 LIS 长度。
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j)
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
}
$O(n \log n)$：维护长度为 $k$ 的上升子序列的最小末尾数组 tail[]，对每个 a[i] 用 lower_bound 替换或追加。
最长公共子序列（LCS）
dp[i][j] = s[0..i) 与 t[0..j) 的 LCS 长度：
- 若
s[i-1] == t[j-1]：dp[i][j] = dp[i-1][j-1] + 1 - 否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
空间可压成两行滚动数组。
编辑距离
dp[i][j] = 将 s[0..i) 变成 t[0..j) 的最少操作数（插入、删除、替换），转移与 LCS 类似，字符不等时取三种操作 +1 的最小值。
最大子段和
dp[i] = 以 a[i] 结尾的最大子段和：dp[i] = max(a[i], dp[i-1] + a[i])，全程维护全局最大值。可 $O(1)$ 空间。
背包 DP
一维数组 dp[j] 表示容量为 $j$ 时的最优值，内层循环容量方向决定背包类型。
0/1 背包
每个物品最多选一次，容量从大到小：
for (int i = 0; i < n; ++i)
for (int j = W; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
完全背包
每个物品无限个，容量从小到大：
for (int i = 0; i < n; ++i)
for (int j = w[i]; j <= W; ++j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
多重背包
物品 $i$ 最多选 c[i] 次：可二进制拆分体积为 $1,2,4,\ldots$ 的 0/1 物品，或用单调队列优化到 $O(nW)$。
二维费用
两种限制（体积 + 重量）时：dp[j][k]，转移与 0/1 类似，两层容量都逆序。
区间 DP
合并、括号匹配、石子合并等：先算小区间，再算大区间。
dp[l][r] = 合并区间 $[l,r]$ 的最优代价，枚举分割点 $k$：
for (int len = 2; len <= n; ++len)
for (int l = 0; l + len - 1 < n; ++l) {
int r = l + len - 1;
dp[l][r] = INF;
for (int k = l; k < r; ++k)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost(l, r));
}
注意：环上区间可先断环复制一倍，或枚举起点。
树形 DP
在树上 DFS，自底向上合并子树信息。常见状态：
dp[u][0/1]：选 / 不选节点 $u$（最大独立集、没有上司的舞会）dp[u]：以 $u$ 为根的子树最优值（换根 DP 需二次 DFS）
void dfs(int u, int fa) {
dp[u] = val[u];
for (int v : adj[u]) if (v != fa) {
dfs(v, u);
dp[u] = max(dp[u], dp[u] + dp[v]); // 依题意合并
}
}
换根 DP：第一次求以 1 为根的答案；第二次 DFS 把根从 $u$ 换到子节点 $v$，用 $O(1)$ 或 $O(\deg)$ 更新父节点贡献。
状压 DP
集合用二进制 mask 表示，第 $i$ 位为 1 表示已选第 $i$ 个元素。
- 旅行商 TSP：
dp[mask][i]已访问集合mask、当前在 $i$ 的最小代价，$n \le 20$ 左右 - 子集枚举：
for (int s = mask; s; s = (s-1) & mask)枚举mask的子集，复杂度 $O(3^n)$ 级别需注意
数位 DP
统计 $[L,R]$ 内满足数位约束的个数（不含前导零、模意义下等）。按位从高到低 DFS，状态通常包括：当前位、是否紧贴上界、是否已开始填数、余数等，用 memo[pos][tight][started][...] 记忆化。
关键：区分「前导零」与「真正数字」的转移，边界 $L,R$ 可分别 DP 后相减。
滚动数组与空间优化
只依赖上一层时：
for (int i = 0; i < n; ++i)
for (int j = 0; j <= W; ++j)
dp[i % 2][j] = ...; // 或两个一维数组 swap
区间 DP 若只依赖更短区间，不能简单滚动，需保留二维。
进阶优化（了解）
| 技巧 | 典型场景 |
|---|---|
| 单调队列优化 | 转移形如 $\max_{k |
| 斜率优化 | 转移可写成直线求最值，维护凸包 |
| 矩阵快速幂 | 固定长度线性递推求第 $n$ 项，$O(k^3 \log n)$ |
| Bitmask + SOS | 子集和 / 超集和 DP |
常见错误
- 循环方向错（0/1 背包正序导致同一物品用多次）
- 状态定义含糊（「前 $i$ 个」是否包含第 $i$ 个）
- 初始化：求最小值时
INF是否够大；空集 / 空串的dp是否为 0 - 答案取错下标（LIS 要
max(dp[i])，不是dp[n-1]）
调试建议
$n \le 15$ 时对拍暴力；打印 DP 表检查边界；画图确认 DAG 无环与转移顺序。
例题
例 1：采药 / 0-1 背包（洛谷 P1048）
$n$ 种物品，体积 $w_i$、价值 $v_i$，背包容积 $W$，每种最多选一次。dp[j] = max(dp[j], dp[j-w_i]+v_i)，$j$ 从 $W$ 到 $w_i$ 逆序。答案 dp[W]。复杂度 $O(nW)$。
例 2：石子合并（区间 DP）
一行 $n$ 堆石子，每次合并相邻两堆，代价为两堆之和，求合并成一堆的最小代价。dp[l][r] 为合并 $[l,r]$ 的最小代价，枚举最后合并位置 $k$：dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l,r))。按区间长度递增计算。复杂度 $O(n^3)$。