01阶段 / 状态 / 转移 / 边界
阶段→状态→转移→边界
- 阶段：按什么顺序填，保证用到的子问题已经算完。
- 状态：子问题的参数。状态少、能转移，才值得建表。
- 转移：当前格由哪些已填格得到。要写清取 max / 加一 / 选或不选。
- 边界：空前缀、容量 0、长度为 1 的区间。漏边界整表漂。
分治：子问题独立同类、不复用。DP：子问题重叠、状态可递推复用；优化型问题还需最优子结构。DP 也用于计数 / 判定，不只优化。
02经典模型
LIS（最长上升）：dp[i] = 以 i 结尾的最长长度，转移看 j<i 且 a[j]<a[i]。O(n²)。O(n log n) 的耐性数组做法标竞赛向。
LCS（最长公共子序列）：c[i][j] 表示 X 前 i 与 Y 前 j。字符相等必须取左上+1；字符不等且上、左等长时取上（平局取上）。终格 4；回溯一条为 BCBA。
| ε | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| ε | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
背包：0-1 每件至多一次，内层容量倒着滚；完全背包可重复，内层正着滚。不要把两种滚动方向写反。
区间 DP：按区间长度从小到大，枚举切点合并。石子合并是典型；细节竞赛向。
03滚动数组
若转移只依赖上一阶段，可只留两行，或一行加小心的覆盖顺序。LCS 可压成 O(min(m,n)) 额外空间，但回溯路径还要旧表或额外存前驱。演示为讲清楚来源，保留整表。
04和分治、贪心怎么分开
- 分治：子问题独立同类、不复用（如归并）。
- DP：子问题重叠、状态可递推复用；优化型还需最优子结构。DP 也用于计数 / 判定，不只优化。
- 贪心：局部选择须有证明能推到全局；课内用具体算法的前提，不把活动选择当 408 必答。