最小成本构造最短回文串问题（在字符串前添加字符）

题目描述

给定一个字符串 s，你可以在它的前面添加任意字符（每次添加一个字符），目标是使得最终的字符串成为一个回文串。每次添加字符的成本为该字符的“添加成本”（假设所有字符添加成本均为 1，但本问题可扩展为不同字符有不同成本）。要求找到添加最少字符（或最小总成本）的方案，使得最终的字符串是回文串，并输出这个最小添加的字符数量（或最小成本）。

简单例子：
s = "abac"
一种方案：在前面添加 "c" → "cabac"，是回文串，添加了 1 个字符。
另一种方案：在前面添加 "a" → "aabac" 不是回文串。
添加 "caba" → "cabaabac" 是回文串但添加了 4 个字符，不是最优。
实际上最优是添加 "c" → "cabac"，最少添加 1 个字符。

问题分析

这个问题可以转化为：
找到原字符串 s 的最长前缀回文子串，设其长度为 len，那么只需要在 s 前面添加 s[len:] 的逆序，即可构成回文串。
例如 s = "abac"，最长前缀回文子串是 "aba"（长度 3），那么需要在前面添加 s[3:] = "c" 的逆序（就是 "c"），得到 "c" + "abac" = "cabac"。

因此，问题转化为求 s 的最长前缀回文子串长度。
一旦找到这个长度 len，需要添加的字符数就是 n - len。

难点：
直接枚举所有前缀并检查是否回文，时间复杂度为 O(n³) 或 O(n²)（如果检查回文用双指针）。
我们可以用区间动态规划预处理出所有子串是否为回文，然后快速查询每个前缀是否回文。

解题步骤

步骤 1：定义状态

设 dp[i][j] 表示字符串 s 的子串 s[i:j+1] 是否是回文串（True/False）。

• i 和 j 是子串的起始和结束索引（包含）。
• 最终我们想要知道所有以 0 开头的前缀 s[0:j] 是否回文，即 dp[0][j] 是否为 True。

步骤 2：状态转移方程

• 如果 i == j，单个字符是回文：dp[i][i] = True。
• 如果 i + 1 == j，两个字符：dp[i][j] = (s[i] == s[j])。
• 如果 j - i >= 2：
  dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]。

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

步骤 3：计算顺序

由于 dp[i][j] 依赖于 dp[i+1][j-1]，即左下角的值，我们需要按长度从小到大计算。
先计算所有长度为 1 的子串，再长度为 2，直到长度为 n。

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

计算完所有 dp[i][j] 后，我们检查 dp[0][j] 中 j 最大且为 True 的那个 j，其长度就是 j+1。
那么需要添加的字符数 = n - (j+1)。

特殊情况：如果整个字符串已经是回文，则不需要添加字符。

举例说明

s = "abac"，n = 4。

1. 初始化 dp 为 False。
2. 长度 1：dp[0][0]=True, dp[1][1]=True, dp[2][2]=True, dp[3][3]=True。
3. 长度 2：
   • dp[0][1] = (s[0]==s[1]) = ('a'=='b') = False
   • dp[1][2] = ('b'=='a') = False
   • dp[2][3] = ('a'=='c') = False
4. 长度 3：
   • dp[0][2] = (s[0]==s[2]) and dp[1][1] = ('a'=='a') and True = True
   • dp[1][3] = ('b'=='c') and dp[2][2] = False and True = False
5. 长度 4：
   • dp[0][3] = (s[0]==s[3]) and dp[1][2] = ('a'=='c') and False = False

现在看前缀：

• dp[0][0] 长度 1 → 是回文
• dp[0][1] 长度 2 → 否
• dp[0][2] 长度 3 → 是回文
• dp[0][3] 长度 4 → 否

最长前缀回文子串长度是 3（"aba"），所以需要添加 4-3=1 个字符。

添加的字符是 s[3:] = "c" 的逆序（就是 "c"），结果 "c" + "abac" = "cabac"，是回文。

算法复杂度

• 时间复杂度：O(n²)，因为要填充 dp 表。
• 空间复杂度：O(n²)，可以优化到 O(n) 如果只按列或行计算，但这里为了清晰理解，先用二维。

代码框架（Python）

def min_add_to_make_palindrome_front(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    
    # 长度为1的子串
    for i in range(n):
        dp[i][i] = True
    
    # 长度为2到n的子串
    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]
    
    # 找最长前缀回文
    max_len = 1
    for j in range(n):
        if dp[0][j]:
            max_len = j + 1
    
    return n - max_len

# 测试
s = "abac"
print(min_add_to_make_palindrome_front(s))  # 输出 1

扩展：如果添加字符有不同成本

如果每个字符 c 有添加成本 cost[c]，则我们需要添加的字符是 s[len:] 的逆序，总成本是这些字符的成本之和。
这时我们仍然用同样的 DP 找到最长前缀回文，然后计算对应后缀的字符总成本即可。

总结

这个问题的核心是用区间DP预处理回文判断，然后寻找最长前缀回文。
一旦找到，后缀的逆序就是需要添加的部分。
这个思路也可以推广到“在字符串后添加字符形成回文”问题，做法类似，只是找最长后缀回文。