让字符串成为回文串的最少插入次数 图解题解

这道题在求什么：最少插几个字符变回文

给一个字符串 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 次。

Python

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]

C++

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = s[i] == s[j] ? dp[i+1][j-1] + 2 : max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return n - dp[0][n-1];
    }
};

Java

import java.util.*;
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return n - dp[0][n - 1];
    }
}