题目描述
思路解析
一句话答案：LeetCode 1312 让字符串成为回文串的最少插入次数：答案 = 串长 n 减最长回文子序列 LPS，落单字符各补镜像。LPS 用区间 DP 求，两端相同内区间加 2、不同取较大，时间 O(n²)、空间可压到 O(n)。
这道题在求什么：最少插几个字符变回文
给一个字符串 s，每次操作能在任意位置插一个字符，问最少插几次能让 s 变回文串。回文串就是正反读一样的串。s = "zzazz" 本身对称答案 0；s = "mbadm" 补 2 个成回文答案 2。要的是最少次数。
为什么不能把插法一个个试过来
长度 n 的串有 n+1 个空位、每位能塞 26 个字母，插一轮分叉一轮，走法指数级涨，长串根本试不完。突破口在反过来问：原串有多少字符能原地留下不动——留得越多，补得越少。
为什么最少插入次数正好是 n 减 LPS
回文串对称，说明串里本有一部分字符摆成对称能留下。能留下的最大一块就是 s 的最长回文子序列 LPS。子序列指按原顺序从 s 挑字符、中间可跳、不要求连着；回文子序列就是挑出来正反读一样，"mbadm" 里的 "mam" 长度 3 就是它的 LPS。
留这 3 个当骨架，剩下的 "b"、"d" 落单没配对。每个落单字符在对称另一侧补个相同字符就成镜像，几个落单补几次，插入次数 = n 减 LPS = 5 减 3 = 2。
两端相同为什么加 2、不同为什么取较大
求 LPS 用区间 DP。DP（动态规划）把「每段子串 s[i..j] 的 LPS」各算一次存进表，大段直接查小段、不重算。dp[i][j] 定义为 s[i..j] 的 LPS 长度——dp 是一张二维表格，行、列指表格的行列、不是字符串本身：i 兼起点下标、j 兼终点下标，都从 0 数起。
两端 s[i]、s[j] 相同时当最外层外壳，里面嵌 s[i+1..j-1] 的最长回文，dp[i][j] = dp[i+1][j-1] + 2，加的 2 是这对外壳。不同时至少丢一个：丢左看 dp[i+1][j]、丢右看 dp[i][j-1] 谁长取谁。对角线 dp[i][i] = 1 是起点。
拿 mbadm 把这张表逐格填出来
填 "mbadm"，下标 0 到 4 是 m、b、a、d、m。对角线 5 个单字符各 dp[i][i] = 1。长度 2 到 4 的区间两端都不同、一律取两侧较大值：dp[0][1]（"m""b"）得 max(1,1)=1，dp[1][3]（"b""d"）内部也全是 1、仍是 1——最外层那对 "m" 合拢前没哪段两端配得上对，一路停在 1。整段 "mbadm" 两端都是 "m"，dp[0][4] = dp[1][3] + 2 = 3 即全串 LPS，答案 = 5 减 3 = 2。
i 从小往大填，内区间为什么全是没算的空格
dp[i][j] 要用 dp[i+1][j-1]、dp[i+1][j] 这些更内更短的区间。要是 i 从小往大填，轮到 dp[i][j] 时 dp[i+1] 那行还没算，取到全是空值。所以 i 从 n-1（n 是串长）倒着到 0、j 从 i+1 正着走。约 n²/2 个格子各常数次比较，时间 O(n²)（大 O 记号是操作次数随规模的量级），dp 表 O(n²) 可压到 O(n)。
边界照套不出错：单字符或已是回文时 LPS = n、答案 0；字符两两不同时 LPS 只 1，得插 n-1 次。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话套路:答案 = 长度减最长回文子序列;两端相同就内区间加 2,不同就丢一端取较大。下面逐格填表套这条规则。
先看骨架:行表示起点 i、列表示终点 j,格子 dp[i][j] 是子串 s[i..j] 的最长回文子序列长度。i > j 没意义(空区间),所以只填右上三角,现在全是「·」表示还没算。
为什么要按这个顺序?因为 dp[i][j] 用到的是更内层、更短的区间 dp[i+1][j-1] / dp[i+1][j] / dp[i][j-1]。只要让 i 从大到小、j 从小到大推,每次要用的内区间都已经算好了。先从对角线(单个字符)起步。
对角线 dp[4][4]:子串就是单个字符 "m",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
对角线 dp[3][3]:子串就是单个字符 "d",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
对角线 dp[2][2]:子串就是单个字符 "a",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
对角线 dp[1][1]:子串就是单个字符 "b",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
对角线 dp[0][0]:子串就是单个字符 "m",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
区间 s[3..4] = "dm":两端 "d" 与 "m" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[4][4]=1;方案二丢右端,看 dp[3][3]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[2..3] = "ad":两端 "a" 与 "d" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[3][3]=1;方案二丢右端,看 dp[2][2]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[1..2] = "ba":两端 "b" 与 "a" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[2][2]=1;方案二丢右端,看 dp[1][1]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[0..1] = "mb":两端 "m" 与 "b" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[1][1]=1;方案二丢右端,看 dp[0][0]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[2..4] = "adm":两端 "a" 与 "m" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[3][4]=1;方案二丢右端,看 dp[2][3]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[1..3] = "bad":两端 "b" 与 "d" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[2][3]=1;方案二丢右端,看 dp[1][2]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[0..2] = "mba":两端 "m" 与 "a" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[1][2]=1;方案二丢右端,看 dp[0][1]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[1..4] = "badm":两端 "b" 与 "m" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[2][4]=1;方案二丢右端,看 dp[1][3]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[0..3] = "mbad":两端 "m" 与 "d" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[1][3]=1;方案二丢右端,看 dp[0][2]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
区间 s[0..4] = "mbadm":两端都是 "m"!相同,这俩能当一层回文外壳。dp[0][4] = 内区间 dp[1][3]=1 + 2 = 3(紫格,蓝格是它依赖的内区间)。
上三角全部填好。右上角 dp[0][4] = 3 表示整个 "mbadm" 的最长回文子序列长度是 3(就是那段 "mam":m 配 m、中间留一个)。
回到原问题:总长 n = 5,能原地保留的回文骨架有 3 个字符,剩下 2 个落单字符各补一个镜像即可。最少插入次数 = 5 - 3 = 2。
复盘整条思路:先把「最少插入」转成「n 减最长回文子序列」;再用区间 DP,从短区间往长区间推,两端相同内区间加 2、不同取两侧最大;右上角即全串 LPS=3,答案 2。
边界:单字符或已是回文都为 0;字符全不同则 LPS=1、需插 n-1 个。
两个追问:落单字符各补镜像所以等于 n 减 LPS;LPS 也等于 s 与逆串的 LCS。
参考代码
class Solution: def minInsertions(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return n - dp[0][n - 1]复杂度
- 时间：O(n²)，n 为字符串长度,上三角约 n²/2 个格子,每格 O(1) 转移
- 空间：O(n²)，dp 表存全部 dp[i][j];可用滚动数组压到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么「最少插入次数」恰好等于 n 减去最长回文子序列长度?
追问这题和最长公共子序列(LCS)有什么联系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
摘樱桃 II
LeetCode 1463 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题