1312. 让字符串成为回文串的最少插入次数

发表于 分类于 阅读次数： Waline： 本文字数： 991 阅读时长 ≈ 3 分钟

考点

  • 区间DP
  • 回文序列

思路

一、问题描述

给定一个字符串 \(s\)，允许在任意位置插入字符，目标是使最终字符串成为回文串，并且插入次数最少。

要求：

  • 只能插入字符，不能删除或修改原有字符；
  • 插入的字符可以是任意字符；
  • 返回最少插入次数。

二、问题建模的核心思想

1. 从“插入”到“保留”

设原字符串长度为 \(n\)。

任何通过插入得到的回文串，都必然完整包含原字符串作为子序列。 因此，最终回文串可以被理解为：

  • 保留原字符串中的某些字符（按原顺序）
  • 对未保留的字符，通过插入的方式进行补齐

关键问题转化为：

在原字符串中，最多能保留多少个字符，使它们本身构成一个回文序列？

这正是最长回文子序列（LPS, Longest Palindromic Subsequence）问题。

2. 最少插入次数与 LPS 的关系

设：

  • 原字符串长度为 \(n\)
  • 最长回文子序列长度为 \(L\)

则有： \[ \boxed{ \text{最少插入次数} = n - L } \] 理由：

  • LPS 中的 \(L\) 个字符可以直接作为最终回文串的“骨架”；
  • 剩下的 \(n - L\) 个字符，必须通过插入其对称字符来补齐；
  • 不可能通过更少的插入覆盖这些未被保留的字符。

因此，本题的本质是：

求字符串的最长回文子序列长度。

三、最长回文子序列的区间 DP 建模

1. 状态定义

使用区间动态规划。

定义： \[ f[i][j] = \text{子串 } s[i..j] \text{ 的最长回文子序列长度} \] 其中：

  • \(i, j\) 为 1-based 下标
  • \(1 \le i \le j \le n\)

2. 边界条件

  • 单个字符天然是回文：

\[ f[i][i] = 1 \]

3. 状态转移方程

考虑区间两端字符 \(s[i]\) 与 \(s[j]\)：

情况一：两端字符相等

\[ s[i] = s[j] \]

这两个字符可以作为回文序列的一对端点，因此： \[ \boxed{ f[i][j] = f[i+1][j-1] + 2 } \] 含义是：

  • 中间区间 \(s[i+1..j-1]\) 的最长回文子序列
  • 再加上左右这两个相等字符

情况二：两端字符不相等

\[ s[i] \ne s[j] \]

最长回文子序列必然来自以下两种情况之一：

  • 不使用左端字符：来自 \(f[i+1][j]\)
  • 不使用右端字符：来自 \(f[i][j-1]\)

取最大值： \[ \boxed{ f[i][j] = \max(f[i+1][j],\ f[i][j-1]) } \]

4. 计算顺序

由于状态 \(f[i][j]\) 依赖更短的区间，需按区间长度递增的顺序进行 DP：

  • 先处理长度为 1
  • 再处理长度为 2、3、……
  • 最终得到 \(f[1][n]\)

四、最终答案的计算

得到最长回文子序列长度 \(f[1][n]\) 后： \[ \boxed{ \text{最少插入次数} = n - f[1][n] } \]

五、算法复杂度分析

  • 状态数量：\(O(n^2)\)
  • 每个状态转移：\(O(1)\)

时间复杂度： \[ O(n^2) \] 空间复杂度： \[ O(n^2) \] 在 \(n \le 500\) 的约束下可以稳定通过。

六、完整参考实现（附注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    // 最大字符串长度（题目约束 n <= 500）
    static const int maxn = 5e2 + 5;

    int minInsertions(string s) {
        int n = s.size();

        // f[i][j] 表示子串 s[i..j]（1-based）的最长回文子序列长度
        int f[maxn][maxn];

        // 边界条件：单个字符的 LPS 长度为 1
        for (int i = 1; i <= n; ++i)
            f[i][i] = 1;

        // 按区间长度递增进行 DP
        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i + len - 1 <= n; ++i) {
                int j = i + len - 1;

                // 若两端字符相等，可以作为回文序列的一对端点
                if (s[i - 1] == s[j - 1]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                }
                // 否则只能从去掉一端的区间中取最大值
                else {
                    f[i][j] = max(f[i][j - 1], f[i + 1][j]);
                }
            }
        }

        // 最少插入次数 = 总长度 - 最长回文子序列长度
        return n - f[1][n];
    }
};