题目描述
思路解析动画文字版
一句话套路:答案 = 长度减最长回文子序列;两端相同就内区间加 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题