入门：序列 DP 与区间 DP 的分野
基于通用算法概念 · 核于 2026-07
速查
- 序列 DP：状态是
dp[i]，语义「前 i 个元素（或以i结尾）的最优」——一维递推。代表：LIS（以i结尾的最长递增子序列）、Kadane 最大子数组和、最长回文子序列（虽是二维但本质序列）。 - 区间 DP：状态是
dp[i][j]，语义「区间[i, j]内的最优」——按区间长度从小到大枚举，内部枚举断点k。代表：最长回文子串、石子合并、戳气球、矩阵连乘。 - LCS（最长公共子序列）：
dp[i][j] = s1[i]==s2[j] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1])，O(nm)。 - LIS（最长递增子序列）：朴素 O(n²)（
dp[i]=max(dp[j])+1, a[j]<a[i]）；二分优化 O(n log n)（维护一个「尾元素最小的递增子序列」数组，二分找第一个 ≥x 的位置替换）。 - 编辑距离：
dp[i][j] = s1[i]==s2[j] ? dp[i-1][j-1] : 1+min(增、删、改)，O(nm)。 - 最长回文子串（区间 DP）：
dp[i][j]表s[i..j]是否回文；len<=2看两端，len>2看dp[i+1][j-1] && s[i]==s[j]。 - 石子合并（区间 DP）：
dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum[i..j]，k枚举断点，前缀和算区间和，O(n³)。 - 区间 DP 枚举顺序：外层枚举区间长度
len（从小到大），中层枚举左端i，算出j=i+len-1，内层枚举断点k——保证算dp[i][j]时它的子区间dp[i][k]、dp[k+1][j]已就绪。 - 状态定义技巧：①问「前 i 个」用
dp[i]；②问「区间」用dp[i][j]；③涉及两序列用dp[i][j]（i、j 各管一序列）；④问「以 i 结尾」用dp[i]+ 内层枚举 j（如 LIS）。 - 空间优化：LCS/编辑距离可压一维（滚动数组，注意
dp[i-1][j-1]要用临时变量暂存）；LIS 二分版只需一个一维数组；区间 DP 难压（依赖i+1行和同行左侧）。 - 与基础 DP 的衔接：基础 DP（背包）的状态是「前 i 个物品 + 容量 j」；本叶把「容量」换成「序列下标」或「区间右端」，套路完全一致——状态定义 + 转移方程 + 计算顺序。
- 进阶顺序：LCS 与 LIS → 编辑距离与区间 DP → 参考。
一、序列 DP：状态落在「前 i 个」或「以 i 结尾」
序列 DP 的状态是一维的 dp[i]，它的语义无外乎两种：
- 「前 i 个元素」的最优：
dp[i]表示考虑了a[0..i-1]后的答案。转移往往从dp[i-1]来（是否纳入a[i]）。 - 「以
a[i]结尾」的最优：dp[i]表示必须以第 i 个元素结尾的最优解。转移要枚举前驱j<i（如 LIS 的dp[i] = max(dp[j])+1）。
两者区别在于「是否强制纳入当前元素」。LIS 是典型的「以 i 结尾」：dp[i] 表示以 a[i] 结尾的最长递增子序列长度，必须枚举所有 j<i 且 a[j]<a[i] 来扩展。Kadane 最大子数组和也是「以 i 结尾」：dp[i] = max(a[i], dp[i-1]+a[i])，要么单开一段，要么接在上一段后面。
新手最容易犯的错：把「以 i 结尾」和「前 i 个」混为一谈。判别技巧：题目问「最长子序列/子数组」时，若要求连续，多半是「以 i 结尾」（Kadane）；若不要求连续，LIS 那种也是「以 i 结尾」但内层枚举 j。而「前 i 个」多用于「能否凑出 / 方案数」类（如爬楼梯、打家劫舍）。
二、区间 DP：状态落在「区间 [i, j]」
区间 DP 处理的是「对一个区间做合并/消除/分割」的问题。状态是 dp[i][j]，表示区间 [i, j] 上的最优解（最小代价、最长长度、是否能……）。它的精髓在于：大区间的解，来自「在某断点 k 切一刀」后的两个小区间的解的组合。
区间 [i, j] 在断点 k 处一分为二：
[i, j] → [i, k] + [k+1, j]
dp[i][j] = 组合(dp[i][k], dp[k+1][j]) // k 从 i 到 j-1 枚举这要求：算 dp[i][j] 时，dp[i][k] 和 dp[k+1][j] 必须已经算好——而它们的区间长度都严格小于 [i, j]。所以区间 DP 的枚举顺序是**「区间长度从小到大」**：
for len in 2..n: // 外层：区间长度（小→大）
for i in 0..n-len: // 中层：左端点
j = i + len - 1 // 算出右端点
for k in i..j-1: // 内层：枚举断点
dp[i][j] = optimize(dp[i][j], combine(dp[i][k], dp[k+1][j]))这是区间 DP 的万能骨架。石子合并、戳气球、矩阵连乘、最长回文子串（的区间版）都套这个结构。最高频 bug：外层不按长度而按下标 i 枚举——会用到尚未计算的子区间，得到错误答案。
三、三大经典一眼速记
| 模型 | 状态 | 转移核心 | 复杂度 |
|---|---|---|---|
| LCS | dp[i][j]（前 i、前 j） | 字符相等 +1，否则取左/上 max | O(nm) |
| LIS | dp[i]（以 i 结尾） | max(dp[j])+1, a[j]<a[i]；二分优化 | O(n²) / O(n log n) |
| 编辑距离 | dp[i][j]（前 i、前 j） | 字符相等免操作，否则 1+min(增,删,改) | O(nm) |
| 最长回文子串 | dp[i][j]（区间是否回文） | 两端相等且内部回文 | O(n²) |
| 石子合并 | dp[i][j]（区间最小代价） | min(dp[i][k]+dp[k+1][j])+sum | O(n³) |
注意 LCS 和编辑距离虽然状态都是 dp[i][j]，但它们不是区间 DP——它们的 i、j 分别管两个序列（双序列 DP），不是「区间两端」。真正的区间 DP 是 i、j 管同一个序列/数组的两端。
四、状态定义的四把钥匙
DP 题难就难在「怎么定义状态」。这里给四条启发式：
- 问「前 i 个 / 前 i 个与容量 j」→ 一维或二维序列 DP：爬楼梯、打家劫舍、背包（容量是第二维）。
- 问「以第 i 个结尾的最优」→ 一维 + 内层枚举前驱：LIS、Kadane、最大乘积子数组。
- 问「两序列的关系」→ 二维
dp[i][j]，i 管 s1 前 i、j 管 s2 前 j：LCS、编辑距离、正则匹配、不同的子序列。 - 问「一个区间上的合并/消除/分割」→ 区间 DP
dp[i][j]，按长度枚举 + 枚举断点：石子合并、戳气球、最长回文子串。
记住这四把钥匙，90% 的序列/区间 DP 题都能对号入座。
五、本叶与三部曲的坐标
- 基础（背包）：状态「前 i 物品 + 容量 j」，选或不选——是 DP 的「Hello World」。
- 本叶（序列区间）：把「容量」换成「序列下标」或「区间右端」，状态变成
dp[i]或dp[i][j]——是 DP 的「主力战场」。 - 进阶（树/数位/换根）：状态落在树结构或数位上，本叶的「状态定义 + 转移方程 + 计算顺序」心智模型完全平移过去。
下一步
理解了序列 DP 与区间 DP 的分野后，下一步先用** LCS 与 LIS** 把「序列 DP」吃透——它们是面试出现频率最高的两道经典，见LCS 与 LIS：序列 DP 双壁。