区间动态规划例题：最小删除次数使字符串成为回文串问题

题目描述
给定一个字符串 s，你可以每次从其中删除一个字符（删除任意位置）。
请计算：最少需要删除多少个字符，才能使得剩下的字符串是一个回文串？
例如：

• 输入："abca"
  输出：1（删除 'b' 或 'c' 后，剩下 "aba" 或 "aca" 是回文串）
• 输入："abcde"
  输出：4（只能保留一个字符，删除其余4个）

这可以等价理解为：找出原字符串中的最长回文子序列，因为删除最少字符 = 保留最多字符形成回文串。
设字符串长度为 n，我们要求最少删除次数 = n - 最长回文子序列的长度。

解题思路
这是一个经典区间DP问题，我们定义状态为：
dp[i][j] 表示字符串 s[i..j]（闭区间）的最长回文子序列的长度。

• 目标：dp[0][n-1]
• 最少删除次数 = n - dp[0][n-1]

状态转移推导
考虑区间 [i, j]：

1. 如果 s[i] == s[j]：
   • 这两个字符可以作为回文子序列的两端，那么 dp[i][j] = dp[i+1][j-1] + 2。
2. 如果 s[i] != s[j]：
   • 要么去掉左端字符，看 s[i+1..j] 的最长回文子序列；
   • 要么去掉右端字符，看 s[i..j-1] 的最长回文子序列；
   • 取两者最大值：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

边界条件：

• 单个字符一定是回文子序列，长度为1：dp[i][i] = 1。
• 空区间（i > j）长度为0，但在递推中我们只用到 i <= j 的情况。

递推顺序
由于 dp[i][j] 依赖于：

• 左下方 dp[i+1][j-1]（更短的区间）
• 左边 dp[i][j-1]
• 下方 dp[i+1][j]
  因此，我们需要按照区间长度从小到大来递推：
  先算所有长度为1的区间，再算长度为2的区间，直到长度为n的区间。

逐步示例
以 s = "abca" 为例，n=4：

1. 初始化 dp[i][i] = 1：

   • (0,0)=1, (1,1)=1, (2,2)=1, (3,3)=1

2. 长度 len=2：

   • [0,1]："ab"：'a' != 'b' → dp=max(dp[0][0],dp[1][1])=max(1,1)=1
   • [1,2]："bc" → 1
   • [2,3]："ca" → 1

3. 长度 len=3：

   • [0,2]："abc"：'a' != 'c' → dp=max(dp[1][2],dp[0][1])=max(1,1)=1
   • [1,3]："bca"：'b' != 'a' → dp=max(dp[2][3],dp[1][2])=max(1,1)=1

4. 长度 len=4：

   • [0,3]："abca"：'a' == 'a' → dp=dp[1][2]+2=1+2=3

最后得到 dp[0][3]=3，即最长回文子序列长度为3。
最少删除次数 = 4 - 3 = 1。

复杂度分析

• 时间复杂度：O(n²)，需要填充二维表格。
• 空间复杂度：O(n²) 用于DP数组，可优化为O(n)（只保存当前行和上一行）。

代码实现（Python）

def minDeletionsToPalindrome(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]:
                dp[i][j] = dp[i+1][j-1] + 2 if length > 2 else 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    longest_pal_len = dp[0][n-1]
    return n - longest_pal_len

# 测试
print(minDeletionsToPalindrome("abca"))  # 1
print(minDeletionsToPalindrome("abcde")) # 4
print(minDeletionsToPalindrome("a"))     # 0
print(minDeletionsToPalindrome("aa"))    # 0

关键点总结

1. 将“最少删除次数”转化为“最长回文子序列长度”，是常见问题转换技巧。
2. 区间DP状态表示区间内最优解，通过比较两端字符是否相等决定转移方向。
3. 递推顺序必须保证在计算大区间时，所依赖的小区间已经计算完成。
4. 该方法同样适用于求最长回文子序列，只是最终答案不同。

这个题目是区间DP的经典应用，你理解了吗？