专题17 · 动态规划2
上一讲的状态是"前 i 个"，这一讲换成"区间 i ~ j"。
区间 DP 的填表顺序不再是从左到右，而是按区间长度从小到大、斜着填——
这是本讲唯一也是最重要的一个新动作。
四道题：最长回文子串、二叉排序树计数（卡特兰数）、回文词、LCS 应用。
状态从"前缀"变成"一段"
线性 DP
状态：dp[i] 或 dp[i][j] = 前缀（前 i 个 / 前 i 与前 j）。
填表顺序：从左到右，因为 dp[i] 只依赖更小的 i。
区间 DP
状态：dp[i][j] = 区间 i ~ j 的最优值。
填表顺序：按长度从小到大，因为 dp[i][j] 依赖更短的区间。
区间 DP 的三层循环（固定套路）
for (int len = 2; len <= n; len++) // ① 先枚区间长度（从短到长） for (int i = 1; i + len - 1 <= n; i++){ // ② 再枚起点 int j = i + len - 1; // 终点就定了 for (int k = i; k < j; k++) // ③ 最后枚分割点 dp[i][j] = max/min/求和(dp[i][j], dp[i][k] 与 dp[k+1][j] 的组合); }
for i ... for j ...，那样算 dp[i][j] 时
里面的小区间还没算出来，结果是 0 或随机值。同一张表，两种顺序，一个对一个错
两头相等 + 里面是回文
状态与转移
dp[i][j] = 子串 s[i..j] 是否是回文（0/1）。
dp[i][j] = (s[i] == s[j]) && (len == 2 || dp[i+1][j-1])
初值：dp[i][i] = 1（单个字符必是回文）。
答案：所有为 1 的格子里长度最大的那个。
为什么依赖"里面一层"
回文去掉两头仍是回文。所以 s[i..j] 是回文
⟺ 两头字符相等 且 s[i+1..j-1] 是回文。
而 s[i+1..j-1] 比它短 2，按长度枚举时已经算好了。
一圈一圈长大：长度 1 → 2 → 3 …
乘法原理 + 加法原理 = 区间DP
为什么可以拆成左右子树
二叉排序树的性质：根左边的都比根小，右边的都比根大。
所以当根是 k 时，左子树只能用 1 ~ k−1，右子树只能用 k+1 ~ n ——
两边互不相干。
两个原理怎么用
乘法原理：左右各自独立 → 方案数相乘 dp[i][k−1] × dp[k+1][j]。
加法原理：根可以是 i ~ j 中任意一个，各类互斥 → 求和。
for (int i = 1; i <= n + 1; i++) for (int j = 0; j <= n; j++)
if (i > j) dp[i][j] = 1; // ★ 空树 = 1 种，最容易漏
for (int len = 1; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++){
int j = i + len - 1; dp[i][j] = 0;
for (int k = i; k <= j; k++) // 枚举谁当根
dp[i][j] += dp[i][k-1] * dp[k+1][j];
}
看每个根怎么把区间切成两半
最少插几个字符变成回文
转化思路（很妙）
把原串 反转让它变成 B，求 LCS(原串, B)。
LCS 就是"正读反读都能对上"的那部分，不需要动；
剩下对不上的字符，每个都要补一个。
答案 = 原串长度 − LCS 长度。
举例
原串 abcda，反转 adcba。
LCS = aba（长度 3）或 ada（长度 3）。
答案 = 5 − 3 = 2（补上 d 和 c 的对称字符）。
原串 vs 反转串，填一张表
换一道题，只改第三层
最长回文子串
for len = 2..n
for i, j = i+len-1
dp[i][j] = (s[i]==s[j]
&& (len==2 || dp[i+1][j-1]));
依赖的是内层区间，不枚分割点。
二叉排序树计数
for len = 1..n
for i, j = i+len-1
for k = i..j
dp[i][j] += dp[i][k-1]*dp[k+1][j];
要枚分割点 k，把区间切成两半。
以后遇到区间 DP，问自己三个问题
① 这格依赖的是"里面一层"还是"切成两半"？
② 空区间 / 长度为 1 的初值是多少？（区间题 80% 的 WA 出在这里）
③ 答案是 dp[1][n] 还是所有区间的最大值？
本讲四个高频失分点
① 第一层循环写成 i
❌ for i … for j … → 算 dp[i][j] 时内层区间还没算。
✅ 第一层必须是 len。
② 空区间初值漏掉
❌ BST 计数里不设 dp[i][j]=1 (i>j) → 全部为 0。
✅ 空树算 一种方案。
③ 子串 / 子序列混淆
❌ 用 LCS 求最长回文子串。
✅ 连续 → 区间DP；可插入 → LCS。
④ 爆 int
❌ 卡特兰数增长极快，n=20 就超 21 亿。
✅ long long。
知识树
动态规划2 ─┬─ 线性DP：LIS / LCS / 回文词（LCS 应用）
└─ 区间DP：最长回文子串（内层依赖）/ 二叉排序树计数（枚分割点）→ 卡特兰数
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
最长回文子串 · PALIN
第1档 · 2 分钟
长度 1 → 1；所有字符相同 → 答案就是长度本身
第2档 · 8 分钟
枚举所有子串 O(n³) 判回文，n ≤ 300 稳过
第3档 · 10 分钟
中心扩展，先只做奇数长度（或只做偶数长度）
第4档 · 15 分钟
区间 DP dp[i][j] = dp[i+1][j−1] && s[i]==s[j]，按长度从小到大枚举
二叉排序树计数 · BST
第1档 · 2 分钟n == 0 或 n == 1 → 1
第2档 · 8 分钟
递归枚举每个根、累加左右子树方案，n ≤ 10 稳过
第3档 · 10 分钟
只做 n ≤ 10 的无记忆化递归
第4档 · 15 分钟
记忆化 f[n] = Σ f[i]·f[n−1−i]（卡特兰数），开 long long
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。