区间动态规划例题：删除字符串中的所有回文子序列的最小删除次数

题目描述

给你一个字符串 s，它仅由字符 'a' 和 'b' 组成。
每次操作，你可以删除 s 中的一个回文子序列（不一定是连续子串，但必须是原序列的子序列）。
目标是最终将整个字符串清空（即删除所有字符）。
求完成目标所需的最小操作次数。

注意：

• 子序列不一定连续，但顺序必须保持。
• 回文子序列定义为正向和反向读相同的序列。
• 每次操作删除一个回文子序列后，剩余字符保持原顺序。

示例：

• 输入：s = "ababa"

• 输出：1

• 解释：整个字符串本身是回文，一次删除即可清空。

• 输入：s = "abb"

• 输出：2

• 解释：第一次删除回文子序列 "bb"，剩下 "a"；第二次删除 "a"。

• 输入：s = "baabb"

• 输出：2

• 解释：第一次删除回文子序列 "baab"，剩下 "b"；第二次删除 "b"。

问题分析

这个问题虽然看起来像“删除回文子串”，但由于允许删除不连续的回文子序列，且字符只有 'a' 和 'b'，因此有重要的性质可利用，但仍然可以用区间动态规划来解决更一般化的版本（比如字符集更大时）。
我们先从一般化DP角度思考：

设 dp[i][j] 表示删除子串 s[i..j]（闭区间）所需的最小删除次数。

步骤1：定义状态

定义：

• dp[i][j]：删除子串 s[i..j] 的最小操作次数。
• 其中 0 ≤ i ≤ j < n，n 是字符串长度。

目标：求 dp[0][n-1]。

步骤2：状态转移方程推导

考虑区间 [i, j]：

1. 如果 s[i] == s[j]
   如果 i == j，则只有一个字符，它本身就是回文，所以 dp[i][j] = 1。
   如果 i + 1 == j，即两个相同字符，它们构成回文，所以 dp[i][j] = 1。
   更一般地，当 s[i] == s[j] 时，我们可以考虑将 s[i] 和 s[j] 与中间部分一起删除。
   注意到，最优解中，s[i] 和 s[j] 可能和中间的某个回文子序列一起删除。
   更精确的分析：

   • 如果 s[i] == s[j]，那么 dp[i][j] 可能等于 dp[i+1][j-1]。
     为什么？因为我们可以让 s[i] 和 s[j] 在第一次删除中和中间部分一起构成一个回文子序列。
     但注意：dp[i+1][j-1] 是删除中间部分的次数，如果中间部分可以在一次删除中完成，那么加上两端的相同字符，整个区间就可以在一次删除中完成。
     但更安全的写法是：
     dp[i][j] = dp[i+1][j-1] 当 dp[i+1][j-1] == 1 时成立，但更一般地，我们需要枚举分割点。
     实际上，标准区间DP思路是：
     dp[i][j] = min(dp[i+1][j-1], dp[i+1][j] + 1, dp[i][j-1] + 1) 并不完全正确。

   更准确的推导：
   我们可以将区间分成两部分：
   dp[i][j] = min(dp[i][k] + dp[k+1][j]) 对 i ≤ k < j。
   但这样会漏掉 s[i] 和 s[j] 一起删除的情况。
   正确的关键观察：

   • 如果 s[i] == s[j]，那么 dp[i][j] 可以等于 dp[i+1][j-1]。
     原因：考虑删除 s[i+1..j-1] 的最优方案，最后一次删除操作中，我们可以将 s[i] 和 s[j] 加入那个回文子序列中（因为它们和两端的某些字符匹配），从而不增加操作次数。
     但这个性质需要严谨证明。不过在此题中，可用以下递推：

     if s[i] == s[j]:
         dp[i][j] = dp[i+1][j-1] if j > i+1 else 1
     else:
         dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
     

     但这种递推在一般字符集时是错误的。
     所以必须用更一般的方法。

2. 更通用的状态转移
   实际上，这是一个经典区间DP模型：

   dp[i][j] = min(dp[i][k] + dp[k+1][j])  for k in [i, j-1]
   

   但这样复杂度 O(n³)。
   然而有一个优化：

   • 如果 s[i] == s[j]，则 dp[i][j] 可以取 dp[i+1][j-1]。
     因为我们可以将 s[i] 和 s[j] 附加到删除 s[i+1..j-1] 的某个回文子序列中，而不增加操作数。
     但需要小心：当 j == i+1 时，dp[i][j] = 1。
     当 j > i+1 时，dp[i][j] = dp[i+1][j-1] 如果 s[i]==s[j]。
     另外，还需考虑一般情况：
     dp[i][j] = min(dp[i][k] + dp[k+1][j]) 对所有 i ≤ k < j。

步骤3：初始化

• 单个字符：dp[i][i] = 1（一个字符本身就是回文子序列）。
• 两个字符：
  • 如果 s[i] == s[i+1]，则 dp[i][i+1] = 1（它们构成回文）。
  • 否则 dp[i][i+1] = 2（先删一个，再删一个）。

步骤4：递推顺序

按区间长度从小到大递推：

1. 长度 = 1：直接初始化。
2. 长度 = 2：按规则计算。
3. 长度从 3 到 n：
   先判断 s[i] == s[j] 则尝试 dp[i][j] = dp[i+1][j-1]。
   然后枚举中间分割点 k 更新：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])。

步骤5：示例推导

以 s = "baabb" 为例，n=5。

初始化：

• dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1, dp[4][4]=1
• 长度2：
  dp[0][1]：'b'!='a' → 2
  dp[1][2]：'a'=='a' → 1
  dp[2][3]：'a'!='b' → 2
  dp[3][4]：'b'=='b' → 1

长度3：

• [0,2]：s[0]='b', s[2]='a' 不同 → dp[0][2]=min(dp[1][2]+1, dp[0][1]+1) = min(1+1, 2+1) = 2
  枚举k=1：dp[0][1]+dp[2][2]=2+1=3 → 保持2
• [1,3]：s[1]='a', s[3]='b' 不同 → dp[1][3]=min(dp[2][3]+1, dp[1][2]+1)=min(2+1,1+1)=2
  k=2: dp[1][2]+dp[3][3]=1+1=2 → 保持2
• [2,4]：s[2]='a', s[4]='b' 不同 → dp[2][4]=min(dp[3][4]+1, dp[2][3]+1)=min(1+1,2+1)=2
  k=3: dp[2][3]+dp[4][4]=2+1=3 → 保持2

长度4：

• [0,3]：s[0]='b', s[3]='b' 相同 → dp[0][3]=dp[1][2]=1
  检查k：k=1: dp[0][1]+dp[2][3]=2+2=4; k=2: dp[0][2]+dp[3][3]=2+1=3 → 保持1
• [1,4]：s[1]='a', s[4]='b' 不同 → dp[1][4]=min(dp[2][4]+1, dp[1][3]+1)=min(2+1,2+1)=3
  k=2: dp[1][2]+dp[3][4]=1+1=2 → 更新为2

长度5：

• [0,4]：s[0]='b', s[4]='b' 相同 → dp[0][4]=dp[1][3]=2
  枚举k：
  k=1: dp[0][1]+dp[2][4]=2+2=4
  k=2: dp[0][2]+dp[3][4]=2+1=3
  k=3: dp[0][3]+dp[4][4]=1+1=2
  最小值是2，与dp[1][3]相同，所以dp[0][4]=2。

结果：dp[0][4] = 2，与示例一致。

步骤6：算法实现（伪代码）

function minRemovePalindromeSubseq(s):
    n = length(s)
    dp = array[n][n] initialized to 0
    for i = 0 to n-1:
        dp[i][i] = 1
    for length = 2 to n:
        for i = 0 to n-length:
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
            for k = i to j-1:
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
    return dp[0][n-1]

步骤7：特性和优化

事实上，当字符集只有 {'a','b'} 时，答案最多为 2。
因为第一次删除所有 'a'（它们是回文子序列，因为全是相同字符），第二次删除所有 'b'。
如果整个字符串原本就是回文，则答案为 1，否则为 2。
但本 DP 方法适用于更一般字符集（例如字母 a~z），可以求出精确的最小删除次数。

总结

这道题展示了区间DP在“删除回文子序列”问题上的应用。
关键点：

1. 状态定义为删除区间的最小操作次数。
2. 状态转移时，如果两端字符相同，则可能减少一次操作（继承中间区间的结果）。
3. 需枚举中间分割点，因为最优解可能由两个独立区间的最优解合并而成。
4. 初始化注意长度为 1 和 2 的情况。

通过这个 DP 框架，即使字符集扩大，也能求出最小操作次数，而不仅限于 {'a','b'} 时的简单情况。