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

题目描述

给定一个字符串 s``，你可以在字符串的**前面**（即开头）添加任意字符，每次添加一个字符的成本为 1。目标是使最终的字符串成为一个**回文串**，并且**总添加成本最小**。你需要返回**最小的添加字符数**（即最小成本），使得 s` 在添加这些字符后变成一个回文串。

换句话说，我们要找到一个最短的回文串 t，使得 t 以 s 作为后缀（即 t 的末尾是 s）。求 t 的长度与 s 的长度之差。

示例 1
输入：s = "aacecaaa"
输出：1
解释：在字符串前添加一个字符 'a'，得到 "aaacecaaa"，这是一个回文串。添加的字符数为 1。

示例 2
输入：s = "abcd"
输出：3
解释：在字符串前添加字符 "dcb"，得到 "dcbabcd"，这是一个回文串。添加的字符数为 3。

解题思路

这个问题可以转化为：寻找字符串 s 的最长前缀回文子串。
为什么？
假设 s 从开头到位置 k 的子串 s[0:k] 是一个回文串（这里 k 是 0-based 的右边界索引），那么我们可以将 s 中剩下的部分 s[k+1:] 反转后添加到字符串前面，从而构成一个回文串。
例如，s = "aacecaaa"，其最长前缀回文子串是 "aacecaa"（索引 0~6），剩下一个字符 'a'，将其反转（还是 'a'）添加到前面，得到 "a" + "aacecaaa" = "aaacecaaa"，是回文串。

因此，最小添加成本 = 字符串长度 - 最长前缀回文子串的长度。

方法 1：暴力查找（非区间 DP）

我们可以从字符串的末尾开始，尝试找到以 s[0] 开头的最长回文子串。
最简单的方法是：

1. 从整个字符串长度开始，检查 s[0:i] 是否是回文串。
2. 如果是，则添加的字符数为 len(s) - i。
3. 否则，减少 i 继续检查。

时间复杂度为 O(n²)，空间复杂度 O(1)。
这种方法虽然简单，但可以作为区间 DP 的引子，帮助我们理解状态定义。

方法 2：区间动态规划解法

我们想用动态规划来高效计算任意子串 s[i:j] 是否是回文串，然后找到以 s[0] 开头的最长回文子串。

步骤 1：状态定义

定义 dp[i][j] 表示子串 s[i:j+1]（即从索引 i 到索引 j 的闭区间）是否是回文串。

• dp[i][j] = true 表示是回文串。
• dp[i][j] = false 表示不是回文串。

步骤 2：状态转移方程

• 如果 i == j，即单个字符，dp[i][j] = true。
• 如果 i + 1 == j，即两个字符，dp[i][j] = (s[i] == s[j])。
• 如果 i + 1 < j，即长度大于 2：

  dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
  

  即首尾字符相同，且去掉首尾后的子串也是回文串。

步骤 3：计算顺序

由于 dp[i][j] 依赖于 dp[i+1][j-1]（即更短的子串），我们应该按子串长度从小到大计算。

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

步骤 4：寻找最长前缀回文子串

在计算完所有 dp[i][j] 后，我们寻找所有以 0 开头的回文子串，即 dp[0][j] == true 的 j，并记录最大的 j（即最长的回文子串的结束索引）。
那么最长前缀回文子串的长度就是 maxLen = max_j + 1。
最终最小添加成本 = n - maxLen。

举例说明

以 s = "abcd" 为例：

1. 长度 n = 4。
2. 计算 dp：
   • 长度 1：(0,0)=true, (1,1)=true, (2,2)=true, (3,3)=true。
   • 长度 2：(0,1): 'a'!='b' → false, (1,2): 'b'!='c' → false, (2,3): 'c'!='d' → false。
   • 长度 3：(0,2): 'a'!='c' → false, (1,3): 'b'!='d' → false。
   • 长度 4：(0,3): 'a'!='d' → false。
3. 检查以 0 开头的回文子串：只有 dp[0][0] = true，所以最长前缀回文子串长度 = 1。
4. 最小添加成本 = 4 - 1 = 3，即添加 "dcb" 到前面。

代码实现（Python）

def minInsertionsToMakePalindrome(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    
    # dp[i][j] 表示 s[i:j+1] 是否是回文串
    dp = [[False] * n for _ in range(n)]
    
    # 初始化：长度为 1 的子串
    for i in range(n):
        dp[i][i] = True
    
    maxPrefixLen = 1  # 最长前缀回文子串的长度，至少为 1（单个字符）
    
    # 按长度从小到大计算
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 2:
                dp[i][j] = (s[i] == s[j])
            else:
                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
            
            # 如果以 0 开头且是回文串，更新最长前缀长度
            if i == 0 and dp[i][j]:
                maxPrefixLen = length
    
    return n - maxPrefixLen

# 测试
print(minInsertionsToMakePalindrome("aacecaaa"))  # 输出 1
print(minInsertionsToMakePalindrome("abcd"))      # 输出 3

复杂度分析

• 时间复杂度：O(n²)，因为要填充 n×n 的 DP 表格。
• 空间复杂度：O(n²)，存储 DP 表格。

扩展思考

1. 如果允许在字符串前后任意位置添加字符，问题就变成了经典的“最小插入次数使字符串变成回文串”问题，可以用区间 DP 直接计算最小插入次数。
2. 如果添加字符的成本不同（例如不同字符有不同成本），则需要调整状态定义，加入成本维度。
3. 本问题也可以用 KMP 算法在 O(n) 时间内解决，方法是构造字符串 s + "#" + reverse(s)，然后计算其最长公共前后缀，从而得到最长前缀回文子串长度。但区间 DP 解法更通用，易于扩展到其他变种。

通过这个例子，你可以看到区间 DP 如何用于回文串相关的构造问题，核心在于定义子串是否为回文串的状态，并利用回文串的递推性质进行填充。