回文，与「藏在串里」的最长回文

回文串就是正着读、反着读一模一样的串： $\texttt{aba}$ 、 $\texttt{noon}$ 、 $\texttt{racecar}$ 。本节要问的不是「整串是不是回文」，而是一个更有嚼头的问题：给一个不一定回文的串，从中按原次序挑出若干字符（不必相邻），能拼出的最长回文有多长？这条挑出来的子序列，就叫最长回文子序列（LPS）。

拿 $s=\texttt{character}$ 做例子。把下标 $0,2,3,4,5$ 的字符挑出来是 $\texttt{carac}$ ——正反都一样，是长度 5 的回文。能不能更长？把所有挑法试遍，最长就是 5。注意它两端对称：最外一对 $\texttt{c}\dots\texttt{c}$ 相同，往里一对 $\texttt{a}\dots\texttt{a}$ 相同，正中留一个 $\texttt{r}$ 。

s=character，挑出下标 0 2 3 4 5 的 c a r a c。弧线把对称的字符两两勾出：外层 c↔c、内层 a↔a、中心 r 独坐——这正是回文「从两端向内成对」的结构。

为什么不能贪心地扫一遍随手配对？因为此刻配哪一对，取决于内层还能配出多长——把某个字符过早用掉，可能挤掉里面一段更优的对称。穷举呢？长度 $n$ 的串子序列有 $2^n$ 条，逐条判回文，指数爆炸。但那句「回文从两端向内成对」正是区间的味道：只盯住一段连续区间的两个端点，就能把大问题剥成更短的子区间——这就是区间 DP 的入口。

状态与转移：只看区间的两个端点

定状态。设 $dp[i][j]$ 表示子串 $s[i..j]$ 这段连续区间里，最长回文子序列的长度。要算它，只需盯住这段区间最外的两个字符 $s_i$ 与 $s_j$ ——它俩相不相等，决定两条截然不同的路。

dp[i][j] 只看两端：相等就把这对字符裹在内层最优回文的两侧，长度 = 内层 dp[i+1][j−1] + 2（来源在左下、内缩一圈）；不等则至少丢一端，取 dp[i+1][j]（丢左）与 dp[i][j−1]（丢右）的较大者。

两端相等（ $s_i=s_j$ ）：这对字符可以且值得做回文的最外一层。把它俩裹在内层 $s[i+1..j-1]$ 的最长回文两侧，长度在内层基础上 $+2$ ：

dp[i][j]=dp[i+1][j-1]+2

两端不等（ $s_i\ne s_j$ ）：这两个端点做不成同一对，那么最长回文里 $s_i$ 与 $s_j$ 至少有一个用不上。于是要么丢掉左端（转成 $dp[i+1][j]$ ），要么丢掉右端（转成 $dp[i][j-1]$ ），谁大取谁：

dp[i][j]=\max\big(dp[i+1][j],\ dp[i][j-1]\big)

边界： $dp[i][i]=1$ （单个字符自成回文），空区间记 $0$ 。答案： $dp[0][n-1]$ 。和其余区间 DP 一样， $dp[i][j]$ 依赖的三个来源（ $dp[i+1][j-1]$ 、 $dp[i+1][j]$ 、 $dp[i][j-1]$ ）都是更短的子区间。所以递推不能按 $i$ 或 $j$ 顺序走，必须按区间长度由短到长——或等价地，让 $i$ 从大到小、 $j$ 从小到大。

本质

回文的最长回文子序列被「连续区间 + 只看两端」拆成一张 $O(n^2)$ 的三角表：每格只依赖左下、下、左三个更短的子区间，一步 $O(1)$ 。 $2^n$ 的枚举就此压进 $n^2/2$ 个上三角格子。「端点相等则收缩 +2，不等则丢一端取大」——这条「收缩 vs 丢弃」的分野是全表的灵魂，也是后面括号匹配、涂色一整族区间问题的共同骨架。

跟着算一遍

用一个短串 $s=\texttt{bcabb}$ （下标 $0..4$ ）走几步，重点盯住长度由短到长、以及每格是「收缩」还是「取大」：

0

对角线（长度 1）。 每个字符自成回文：

dp[i][i]=1

。这是整张三角表的地基。

1

长度 2：看两端等不等。

dp[3][4]

：

s_3=\texttt{b}=s_4

相等 →

0+2=2

（内层为空记 0）。而

dp[0][1]

：

s_0=\texttt{b}\ne s_1=\texttt{c}

→

\max(dp[1][1],dp[0][0])=1

。

2

长度 3～4：

dp[2][4]

（

\texttt{abb}

）：

s_2=\texttt{a}\ne s_4=\texttt{b}

→

\max(dp[3][4],dp[2][3])=\max(2,1)=2

。

dp[1][4]

（

\texttt{cabb}

）：

s_1=\texttt{c}\ne s_4=\texttt{b}

→

\max(dp[2][4],dp[1][3])=\max(2,1)=2

。

3

长度 5，整段 $[0,4]$ （

\texttt{bcabb}

）：

s_0=\texttt{b}=s_4

相等 → 收缩到内层

dp[1][3]+2

。

dp[1][3]=\texttt{cab}

端点不等取大得

1

，故

dp[0][4]=1+2=3

——最长回文子序列长 3（如

\texttt{bab}

或

\texttt{bcb}

）。

下面的演示会把三角表按长度一层层填满，高亮每个

dp[i][j]

是「相等收缩（左下）」还是「不等取大（下 / 左）」。改改字符串，看表实时重算。

看三角表一层一层长出来 · 相等收缩、不等取大

当前串 "bcabb"（长度 5）· 最长回文子序列长度 dp[0][4] = 3 · 表内每格 dp[i][j] = 子串 s[i..j] 的最长回文子序列长。

j=0·b

j=1·c

j=2·a

j=3·b

j=4·b

i=0·b

i=1·c

i=2·a

i=3·b

i=4·b

1

·

1

·

1

·

1

·

1

当前计算依赖来源被选转移已确定

dp[i][i]=1

对角线（区间长度 1）：单个字符自成回文，dp[i][i]=1。

进度

已暂停，第 1 步，共 12 步，1 倍速

深化：最少插入构回文，与「括号 / 涂色」同族

换一个看似不同的问题：给一个串，每次可在任意位置插入一个字符，问最少插入几次能让整串变回文？它和最长回文子序列其实是同一枚硬币的两面——

\text{minInsert}=n-\text{LPS}

道理很直白：串里那条最长回文子序列本就对称，一个字符都不用动；剩下的 $n-\text{LPS}$ 个「落单」字符，每个补一个镜像伙伴即可配对。所以求最少插入，等价于求最长回文子序列，再用总长减去它。也可以直接写一张区间 DP： $f[i][j]$ = 把 $s[i..j]$ 补成回文的最少插入；端点相等则 $f[i+1][j-1]$ ，不等则 $\min(f[i+1][j],f[i][j-1])+1$ ——与上面的收缩 / 取大结构一模一样，只是把 +2 换成 +0、把 max 换成 min+1。

abcda 不是回文：最长回文子序列 aba（长 3），落单的 c、d 里需补 2 个字符（= 5 − 3），补成 abcdcba。虚线框是新插入的镜像字符。

这套「端点相等省一步、不等再拆」的骨架，正是一整族区间问题的共同模板。括号 / 序列匹配同理： $s_i$ 与 $s_j$ 若能配成一对括号，问题落到内层 $[i+1,j-1]$ ，否则枚举分割点拆两段。涂色（区间刷漆）也一样：两端颜色相同则一笔顺带覆盖、省一次（ $f[i][j]=\min(f[i+1][j],f[i][j-1])$ ），不同则枚举分割点两段相加——正是例题 P4170。记住这条主线：区间 DP 的两端，要么配对内缩、要么拆点分治；回文是它最干净的入门形态。

下面的演示把「最少插入构回文」逐步跑给你看：双指针从两端逼近，相等内缩、不等就在较省一侧补一个镜像字符，直到补成回文。核对它的插入次数与上方三角表同一答案。

原串 "google"（长度 6）· 最长回文子序列 4 · 最少插入 2 次 = 长度 6 − 最长回文子序列 4 · 补齐后回文 "elgoogle"。

双指针 i → 与 ← j 从两端向内收缩已插入 0/2

0g

1o

2o

3g

4l

5e

逐步锁定的回文外壳（从两端向内长；… 为待定中段）第 0/4 步

google

点播放或 下一步 开始：让 i、j 从两端逼近。相等则内缩（天然对称，0 插入）；不等则在较省的一侧补一个对端字符（+1），直到指针相遇——补齐的串即回文。

进度

已暂停，第 1 步，共 6 步，1 倍速

别混淆：回文子序列 vs 回文子串

本节的 $dp[i][j]$ 求的是最长回文子序列（字符可不相邻，端点相等就 $+2$ ）。另有一类求最长回文子串（必须连续），转移与判定都不同：区间 DP 版本记 $g[i][j]$ = 「 $s[i..j]$ 整段是否回文」， $g[i][j]=g[i+1][j-1]\ \&\&\ (s_i=s_j)$ ，专业解法还有 Manacher 的 $O(n)$ 。两者状态含义不同、答案不同，别把「子序列」的 $+2$ 套到「子串」上。本页只讲子序列一族。

为什么按长度递推：填表顺序与复杂度

回文区间 DP 的表是个上三角（只有 $i\le j$ 才是合法区间）。 $dp[i][j]$ 的三个来源 $dp[i+1][j-1]$ 、 $dp[i+1][j]$ 、 $dp[i][j-1]$ 的区间长度都比 $[i,j]$ 短。只要先把所有短区间算完，长区间要用的就都已就绪。这就是「外层枚举长度 $L=2\ldots n$ 、内层枚举左端点 $i$ 」的由来——最长回文子序列没有分割点那层枚举，故是 $O(n^2)$ （括号 / 涂色因带分割点枚举升到 $O(n^3)$ ）：

for i = 0 … n-1:                 // 长度 1：单字符自成回文
  dp[i][i] = 1
for 长度 L = 2 … n:               // ★外层枚举区间长度，由短到长
  for 左端点 i = 0 … n-L:
    j = i + L - 1
    if s[i] == s[j]:              // 端点相等 → 收缩内层再 +2
      dp[i][j] = (L == 2 ? 0 : dp[i+1][j-1]) + 2
    else:                        // 端点不等 → 丢一端取大
      dp[i][j] = max(dp[i+1][j], dp[i][j-1])

这份「外层长度、端点决定收缩或取大」的骨架，把它记死：它是回文、最少插入、括号匹配、涂色一整族题的通用模具。

例题

P1435[IOI2000] 回文字串IOI2000普及/提高-

题意

给一个串，每次可在任意位置插入一个字符，求使整串成为回文串的最少插入次数。

对应关系

正是本页深化的最少插入 = $n-\text{LPS}$ 。可直接写区间 DP：

dp[i][j]

= 补成回文的最少插入，端点相等

dp[i+1][j-1]

、不等

\min(dp[i+1][j],dp[i][j-1])+1

——与最长回文子序列同一收缩结构，参考代码用的就是它。

为什么选它

经典的 IOI 入门题，把「插入构回文」和「最长回文子序列」两个视角焊在一起的最佳载体：收缩过程一步步演示极佳，也让你亲手确认

n-\text{LPS}

这条恒等式。注意串可能含大小写混合与数字，全部按字符比较即可。

转移 · 复杂度

端点相等

dp[i][j]=dp[i+1][j-1]

；不等

dp[i][j]=\min(dp[i+1][j],dp[i][j-1])+1

。外层长度、内层左端点；时间

O(n^2)

。

参考代码（最少插入 · 区间 DP）

C++

在洛谷打开 P1435

#include <iostream>
#include <cstring>
using namespace std;

#define MX 1005
char s[MX];
int len;
int dp[MX][MX];   // dp[i][j]：把子串 s[i..j] 补成回文的最少插入次数

int main()
{
    cin >> (s + 1);                          // 1-based：字符放在 s[1..len]
    len = strlen(s + 1);

    // ★按区间长度由短到长递推；长度 1 的子串已是回文，dp 默认 0
    for (int L = 2; L <= len; L++)
    {
        for (int i = 1; i + L - 1 <= len; i++)
        {
            int j = i + L - 1;
            if (s[i] == s[j])                // 两端天然对称，直接内缩
            {
                dp[i][j] = dp[i + 1][j - 1];
            }
            else                             // 补一端与对端配对，代价 +1，取较省的一侧
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }

    cout << dp[1][len] << endl;              // dp[1][len] 即整串补成回文的最少插入次数
    return 0;
}
// TAG: 区间DP 回文 最少插入

P4170[CQOI2007] 涂色CQOI2007普及+/提高

题意

一段木板每格有目标颜色，每次可把一段连续区间刷成同一颜色（后刷覆盖先刷）。求刷出目标配色的最少次数。

对应关系

端点决定收缩 / 分治的另一面孔：

dp[i][j]

= 刷好

[i,j]

的最少次数。两端颜色相同时，可让某一端的一笔顺带覆盖到另一端，省一次：

dp[i][j]=\min(dp[i+1][j],dp[i][j-1])

；不同则枚举分割点

k

把两段各自刷再相加。与回文的「端点相等省一步」如出一辙。

为什么选它

省选级区间 DP 的招牌题：它把回文那条「端点同色 → 优化一步」的直觉，落到「刷漆次数」上，还多出一层分割点枚举（故

O(n^3)

）。写通它，你就掌握了区间 DP「端点特判 + 分治枚举」的完整模具。

转移 · 复杂度

s_i=s_j:\ dp[i][j]=\min(dp[i+1][j],dp[i][j-1])

；否则

dp[i][j]=\min_k(dp[i][k]+dp[k+1][j])

。外层长度、内层左端点、最内分割点；时间

O(n^3)

。

参考代码（端点同色优化 · 分割点枚举）

C++

在洛谷打开 P4170

#include <iostream>
#include <cstring>
using namespace std;

#define MX 55
char s[MX];
int len;
int dp[MX][MX];   // dp[i][j]：把区间 s[i..j] 刷成目标颜色的最少次数

int main()
{
    cin >> (s + 1);
    len = strlen(s + 1);

    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= len; i++)
    {
        dp[i][i] = 1;                        // 单格必刷一次
    }

    for (int L = 2; L <= len; L++)
    {
        for (int i = 1; i + L - 1 <= len; i++)
        {
            int j = i + L - 1;
            if (s[i] == s[j])                // ★端点同色：一笔可顺带覆盖，省一次
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
            }
            else                             // 否则枚举分割点，两段各自刷再相加
            {
                for (int k = i; k <= j - 1; k++)
                {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
    }

    cout << dp[1][len] << endl;
    return 0;
}
// TAG: 区间DP 回文 端点同色 涂色

练习

P3205[HNOI2010] 合唱队区间 DP 按端点「插入方向」计数：每个人从左端或右端插入当前队列，设 dp[i][j][0/1] 表示区间 [i,j] 且最后一个是从左 / 右插入的方案数，转移按新人比端点高矮决定能从哪侧接上。与回文的「端点决策」同源，只是把「取值」换成「计数」。在洛谷打开

P2426删数区间删除合并：dp[i][j] = 删空区间 [i,j] 能得的最大价值。单个数单独删，或若两端满足给定条件可一起删并加权；否则枚举分割点把区间拆两段相加。端点特判 + 分割点枚举，正是本页涂色一族的骨架。在洛谷打开

回文 / 括号

本课摘要