最长回文子序列的最少插入次数

我将为你讲解“最长回文子序列的最少插入次数”这道线性动态规划题目。这是一个字符串处理与回文序列相关的经典问题，通过动态规划可以高效求解。

题目描述

给定一个字符串 s，你可以在字符串的任意位置插入任意字符。请计算出使该字符串变成回文串的最少插入次数。

例如：

• 输入 s = "abca"，输出 1（插入 'c' 得到 "acbca" 或插入 'b' 得到 "abcba"）。
• 输入 s = "abcde"，输出 4（例如变成 "abcdedcba"）。

解题思路分析

我们需要将给定字符串转换为回文串，且只能通过插入字符实现。关键在于找到原字符串中的最长回文子序列（Longest Palindromic Subsequence, LPS），因为这部分已经构成回文，不需要额外插入。对于不在最长回文子序列中的字符，我们需要在对称位置插入相同字符来匹配。

因此：

• 设原字符串长度为 n，最长回文子序列长度为 lps。
• 最少插入次数 = n - lps。

接下来问题转化为：如何求最长回文子序列的长度？我们可以用动态规划解决。

详细解题步骤

步骤1：定义状态

定义 dp[i][j] 表示字符串 s 在子区间 [i, j] 内的最长回文子序列的长度，其中 0 <= i <= j < n。

步骤2：状态转移方程

我们考虑子串 s[i..j]：

1. 如果 s[i] == s[j]，那么这两个字符可以贡献给回文子序列：
   • 如果 i == j，dp[i][j] = 1（单个字符本身就是回文）。
   • 如果 i + 1 == j，dp[i][j] = 2（两个相同字符）。
   • 否则，dp[i][j] = dp[i+1][j-1] + 2（在内部子串的最长回文子序列两端加上这两个相同字符）。
2. 如果 s[i] != s[j]，那么这两个字符不可能同时作为回文子序列的两端，我们只能选择其中一个：
   • dp[i][j] = max(dp[i+1][j], dp[i][j-1])（要么去掉左端字符，要么去掉右端字符，取最大值）。

步骤3：初始化

• 对角线上的元素 dp[i][i] = 1，因为单个字符是长度为1的回文子序列。
• 对于 i > j 的情况，子串为空，长度为0（但在我们的循环中不会用到）。

步骤4：计算顺序

由于状态转移依赖于 i+1 和 j-1，即更短的子串，我们需要按照子串长度从小到大的顺序计算：

• 外层循环：长度 len 从 2 到 n。
• 内层循环：起始索引 i 从 0 到 n - len，计算 j = i + len - 1。

步骤5：获取结果

最长回文子序列的长度为 dp[0][n-1]。
最少插入次数 = n - dp[0][n-1]。

示例推导

以 s = "abca" 为例，n = 4。

1. 初始化 dp 表（n x n 矩阵，初始为0）：

   dp[i][i] = 1 对所有 i。
      a  b  c  a
   a  1  0  0  0
   b  0  1  0  0
   c  0  0  1  0
   a  0  0  0  1
   

2. 计算长度 len = 2 的子串：

   • "ab": s[0]≠s[1]，dp[0][1] = max(dp[1][1], dp[0][0]) = max(1,1) = 1。
   • "bc": s[1]≠s[2]，dp[1][2] = max(dp[2][2], dp[1][1]) = max(1,1) = 1。
   • "ca": s[2]≠s[3]，dp[2][3] = max(dp[3][3], dp[2][2]) = max(1,1) = 1。
     更新后：

   a  b  c  a
   a  1  1  0  0
   b  0  1  1  0
   c  0  0  1  1
   a  0  0  0  1
   

3. 计算长度 len = 3 的子串：

   • "abc": s[0]≠s[2]，dp[0][2] = max(dp[1][2], dp[0][1]) = max(1,1) = 1。
   • "bca": s[1]≠s[3]，dp[1][3] = max(dp[2][3], dp[1][2]) = max(1,1) = 1。
     更新后：

   a  b  c  a
   a  1  1  1  0
   b  0  1  1  1
   c  0  0  1  1
   a  0  0  0  1
   

4. 计算长度 len = 4 的子串：

   • "abca": s[0]==s[3]，所以 dp[0][3] = dp[1][2] + 2 = 1 + 2 = 3。
     最终 dp：

   a  b  c  a
   a  1  1  1  3
   b  0  1  1  1
   c  0  0  1  1
   a  0  0  0  1
   

最长回文子序列长度 lps = dp[0][3] = 3。
最少插入次数 = 4 - 3 = 1。

代码实现

def minInsertions(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 初始化：单个字符的回文长度为1
    for i in range(n):
        dp[i][i] = 1
    
    # 按子串长度递增计算
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = 2
                else:
                    dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    lps_length = dp[0][n-1]
    return n - lps_length

# 测试
print(minInsertions("abca"))   # 输出 1
print(minInsertions("abcde"))  # 输出 4

复杂度分析

• 时间复杂度：O(n²)，因为我们需要填充一个 n x n 的 dp 表。
• 空间复杂度：O(n²)，用于存储 dp 表。可以优化到 O(n) 使用滚动数组，但这里为了清晰展示逻辑，使用二维表。

关键点总结

1. 将问题转化为求最长回文子序列的长度，因为已回文的部分无需插入。
2. 动态规划的状态设计为子串的最长回文子序列长度。
3. 状态转移时，根据两端字符是否相等分为两种情况。
4. 最终答案即字符串长度减去最长回文子序列长度。

这种思路也适用于类似“最少删除次数使字符串变成回文”的问题（同样 = n - lps），只是操作由“插入”变为“删除”。