区间动态规划例题：最小插入次数构造最短回文串问题（在字符串前添加字符）

1. 问题描述

给定一个字符串 s，你可以在它的前面添加任意字符。每次添加一个字符的成本为 1。
目标是添加最少数量的字符，使得整个字符串变成一个回文串。
求最小插入次数。

示例 1
输入：s = "ab"
输出：1
解释：在字符串前添加一个 'b'，得到 "bab"，成为回文串。

示例 2
输入：s = "abc"
输出：2
解释：在字符串前添加 "cb"，得到 "cbabc"，成为回文串。

示例 3
输入：s = "a"
输出：0
解释：单个字符已经是回文串。

示例 4
输入：s = "abcd"
输出：3
解释：添加 "dcb" 得到 "dcbabcd"。

2. 问题分析

我们只能在原字符串的前面添加字符，不能修改或删除原字符串的任何字符。
设原字符串长度为 n。
添加字符后，最终回文串的长度是 n + k，其中 k 是添加的字符数。
由于添加的字符只能在前面，最终的字符串可以写成：

添加的 k 个字符 + 原字符串 s

并且整体必须是回文串。

关键观察：
如果我们从最终回文串的中间位置考虑，可以推出：原字符串 s 的某个后缀必须是回文串。
为什么？
因为添加的字符只能放在前面，所以最终回文串的前 k 个字符是添加的，后 n 个字符是原串 s。
由于回文的对称性，最终串的前 k 个字符必须与最终串的后 k 个字符完全相反（镜像对应）。
最终串的后 k 个字符来自原串 s 的后 k 个字符。
所以，原串 s 的后 k 个字符必须是回文串（因为它们会与添加的字符对称）。

更精确地说：
设最终回文串的长度为 m = n + k。
回文要求：位置 i 的字符 = 位置 m-1-i 的字符。
当 i < k 时，这些字符是我们添加的，而位置 m-1-i 的字符来自原串 s 的末尾部分。
为了最小化 k，我们希望原串 s 的最长后缀回文尽可能长，这样我们只需要在它前面补上缺失的部分即可。

结论：
问题转化为：找到原串 s 的最长后缀回文（即从某个位置 j 到字符串末尾的子串是回文串）。
设这个后缀回文的起始索引为 j（0 ≤ j ≤ n-1），长度为 n-j。
那么我们只需要在原串前添加 s[j-1]s[j-2]...s[0] 这些字符（即原串的前 j 个字符的逆序），就能构造出回文串。
添加的字符数 = j。
因此，最小添加字符数 = 最小的 j，使得 s[j..n-1] 是回文串。
也就是使 s[0..j-1] 的逆序补在前面能形成回文。

3. 动态规划解法（区间 DP 判断回文子串）

我们可以用区间 DP 快速判断任意子串 s[i..j] 是否为回文串。
定义 dp[i][j] 表示子串 s[i..j] 是否为回文串（True/False）。
转移方程：

• 如果 i == j，dp[i][j] = True。
• 如果 i+1 == j，dp[i][j] = (s[i] == s[j])。
• 如果 i+1 < j，dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])。

我们可以从长度为 1 的子串开始，逐步扩展到整个字符串。

算法步骤：

1. 计算所有 dp[i][j]。
2. 从 j = 0 到 n-1，寻找最大的 j，使得 dp[j][n-1] 为 True。这个 j 是后缀回文的起始位置。
3. 需要添加的字符数 = j。
4. 构造结果：添加的字符是 s[j-1]s[j-2]...s[0]。

例子：s = "ab"

• dp[0][0] = True, dp[1][1] = True, dp[0][1] = False。
• 后缀回文：dp[1][1] 是 True（后缀 "b" 是回文），j=1。
• 添加的字符数 = 1。
• 添加的字符是 s[0] 的逆序，即 "a" 的逆序是 "a"，但注意我们需要的是 s[0..j-1] 的逆序，这里 j=1，s[0..0] 的逆序是 "a"？等一下，这里要小心。

检查：j=1 表示后缀 s[1..n-1] = "b" 是回文。
那么需要在前面添加 s[0..j-1] = s[0..0] = "a" 的逆序，即 "a"。
添加后得到 "a"+"ab" = "aab"，这不是回文。
哪里错了？
纠正：我们需要添加 s[0..j-1] 的逆序，并且这个逆序会放在原串前面，与原串的后缀对称。
但当我们添加 s[0..j-1] 的逆序时，最终字符串是：

reverse(s[0..j-1]) + s

并且这个字符串必须是回文。
对于 s="ab", j=1, reverse(s[0..0]) = "a"，得到 "aab"，不是回文。
所以我们的推理有误。

4. 正确推理与 DP 状态定义

设最终回文串为 t，长度为 n+k，t[0..k-1] 是我们添加的，t[k..n+k-1] 是原串 s。
回文要求：t[i] = t[n+k-1-i] 对所有 i 成立。
考虑 i 从 0 到 k-1：
t[i] 是我们添加的，t[n+k-1-i] 是原串 s 的位置 (n+k-1-i)-k = n-1-i。
所以 t[i] 必须等于 s[n-1-i]。
这意味着我们添加的字符串正好是 s[n-1-i] 的倒序，i 从 0 到 k-1，即 s[n-1]s[n-2]...s[n-k] 的倒序？不，是 s[n-1-i] 的序列。

更直接地说：我们添加的 k 个字符是 s[n-1], s[n-2], ..., s[n-k] 吗？
检查：i=0 时，t[0] = s[n-1]。
i=1 时，t[1] = s[n-2]。
...
i=k-1 时，t[k-1] = s[n-k]。
所以添加的字符串是 s[n-1], s[n-2], ..., s[n-k] 这个序列。
但添加的字符串是放在前面，所以最终串是：

s[n-1] s[n-2] ... s[n-k]  s[0] s[1] ... s[n-1]

这个整体必须是回文。
回文对称性要求：前 k 个字符 = 后 k 个字符的逆序。
后 k 个字符是 s[n-k] ... s[n-1] 吗？ 不对，后 k 个字符是 s[n-1], s[n-2], ..., s[n-k] 的逆序？我们仔细看。

最终串 t 的后 k 个字符是 t[n+k-1], t[n+k-2], ..., t[n]？
不对，长度是 n+k，索引 0..n+k-1。
后 k 个字符是 t[n+k-1], t[n+k-2], ..., t[n] 对应原串的 s[n-1], s[n-2], ..., s[n-k]。
所以后 k 个字符是 s[n-1], s[n-2], ..., s[n-k]。
前 k 个字符是我们添加的，也就是 s[n-1], s[n-2], ..., s[n-k]。
所以前 k 个字符必须等于后 k 个字符，这总是成立。
那么还剩下中间的部分 t[k..n-1] 必须自己是回文。
注意 t[k..n-1] 对应原串 s[0..n-k-1]。
所以条件变为：原串的前缀 s[0..n-k-1] 必须是回文串。
这样最终串才是回文。

因此：
我们需要找到最长的前缀回文 s[0..x]，设其长度为 len = x+1。
那么 k = n - len 就是需要添加的字符数。
因为我们保留这个前缀回文不动，后面部分通过在前面添加字符来镜像补全。

例子：s="ab"
最长前缀回文是 s[0..0] = "a"，len=1，k=2-1=1，添加 1 个字符。
添加的字符是 s[1] = "b"，得到 "b"+"ab" = "bab"，是回文。正确。

例子：s="abc"
最长前缀回文是 "a"，len=1，k=3-1=2，添加 "cb"，得到 "cbabc"，正确。

5. 动态规划解法（找最长前缀回文）

我们可以用刚才的 dp[i][j] 表示 s[i..j] 是否为回文串。
要找的是所有 dp[0][j] 为 True 的最大的 j。
设这个最大的 j 为 maxJ，则最长前缀回文的长度是 maxJ+1。
需要添加的字符数 = n - (maxJ+1)。

算法步骤：

1. 初始化 n = len(s)，dp 为 n×n 的 False 矩阵。
2. 对长度为 1 的子串，dp[i][i] = True。
3. 对长度为 2 的子串，dp[i][i+1] = (s[i] == s[i+1])。
4. 对长度 L 从 3 到 n，枚举起始点 i，j = i+L-1，dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])。
5. 找出最大的 j 使得 dp[0][j] 为 True，设这个 j 为 right。
6. 添加的字符数 = n - (right+1)。
7. 添加的字符是 s[n-1], s[n-2], ..., s[right+1] 的逆序？等等，我们要构造最终串的话，需要在前面添加 s[right+1..n-1] 的逆序，即 s[n-1]s[n-2]...s[right+1]。

验证：s="ab"，n=2，dp[0][0]=True，dp[0][1]=False，right=0，添加数=2-(0+1)=1，添加的字符是 s[1] 的逆序（只有一个字符"b"），得到 "b"+"ab"="bab"，正确。

6. 代码实现（Python 风格伪代码）

def minInsertionsToMakePalindrome(s):
    n = len(s)
    if n == 0:
        return 0
    dp = [[False] * n for _ in range(n)]
    # 长度为 1
    for i in range(n):
        dp[i][i] = True
    # 长度为 2
    for i in range(n-1):
        dp[i][i+1] = (s[i] == s[i+1])
    # 长度 >= 3
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1]
    # 找最长前缀回文
    right = 0
    for j in range(n):
        if dp[0][j]:
            right = j
    add_len = n - (right + 1)
    return add_len

时间复杂度：O(n²)。
空间复杂度：O(n²)。

7. 优化（中心扩展法）

我们不需要计算所有子串的回文状态，只需要找以索引 0 开头的最长回文子串。
可以用中心扩展法：
遍历每个中心（可能是单个字符或两个字符之间），从中心向两边扩展，但必须保证左边界是 0。
当左边界到达 0 时，记录此时右边界的位置。
取所有中心扩展中右边界最大的值，即为最长前缀回文的结束位置。

步骤：

1. 初始化 right = 0。
2. 中心 i 从 0 到 n-1：
   • 以 i 为中心，l = i, r = i，扩展直到 l≥0 且 r<n 且 s[l]==s[r]。
   • 如果 l==0，则 right = max(right, r)。
   • 以 i 和 i+1 为中心，l = i, r = i+1，扩展直到 l≥0 且 r<n 且 s[l]==s[r]。
   • 如果 l==0，则 right = max(right, r)。
3. 添加的字符数 = n - (right+1)。

例子：s="ab"
中心 i=0: 单字符扩展，l=0,r=0，l==0，right=0。
中心 i=0: 双字符扩展，l=0,r=1，s[0]!=s[1]，停止。
中心 i=1: 单字符扩展，l=1,r=1，l!=0，忽略。
最终 right=0，添加数=1。

代码：

def minInsertionsToMakePalindrome(s):
    n = len(s)
    right = 0
    for center in range(n):
        # 奇数长度
        l, r = center, center
        while l >= 0 and r < n and s[l] == s[r]:
            if l == 0:
                right = max(right, r)
            l -= 1
            r += 1
        # 偶数长度
        l, r = center, center+1
        while l >= 0 and r < n and s[l] == s[r]:
            if l == 0:
                right = max(right, r)
            l -= 1
            r += 1
    return n - (right + 1)

时间复杂度：O(n²) 最坏，但平均比 DP 快。
空间复杂度：O(1)。

8. 总结

这个问题本质上是在原串前面添加字符，使得整体成为回文串。
通过分析，我们转化为寻找最长前缀回文，然后补充剩余部分的逆序到前面。
可以用区间 DP 或中心扩展法解决。
最终答案 = 字符串长度 - 最长前缀回文的长度。