删除回文子数组的最小操作次数

题目描述

给定一个字符串 s，你可以每次删除其中的一个 回文子串（即正读反读相同的连续子串），删除后剩余部分会拼接起来。
请计算删除整个字符串 s 所需的最小操作次数。

示例

• 输入：s = "ababa"
  输出：1
  解释：整个字符串本身就是回文串，一次删除即可。
• 输入：s = "abb"
  输出：2
  解释：可以先删除 "bb"，再删除 "a"；或者先删除 "a"，再删除 "bb"。
• 输入：s = "baac"
  输出：2
  解释：先删除 "aa"，再删除 "bc"。

数据范围

• 1 ≤ |s| ≤ 100
• 字符串仅由小写字母组成。

问题分析

这个问题是区间动态规划的典型应用，因为我们需要考虑字符串的子区间，并计算其最小删除次数。
关键点是：一次可以删除一个回文子串，而不限于单个字符。
因此，如果整个区间已经是回文串，一次操作即可；否则需要分割区间，通过多次操作完成。

解题步骤

步骤 1：定义状态

设 dp[i][j] 表示删除子串 s[i:j]（包含 i 和 j）所需的最小操作次数。
这里 i 和 j 是闭区间索引，从 0 到 n-1，n 为字符串长度。

步骤 2：初始状态

• 对于长度为 1 的子串（即 i == j）：它本身就是回文串，所以 dp[i][i] = 1。
• 其他情况初始化为一个较大值（比如无穷大），在递推中更新。

步骤 3：状态转移

我们按区间长度从小到大计算。设当前区间为 s[i:j]，长度 len = j - i + 1。

情况 1：整个区间是回文串

如果 s[i] == s[j] 且内部也是回文串（可以通过预处理或动态判断），则 dp[i][j] = 1。
但注意：判断内部回文需要 O(1) 时间，我们可以先预处理 isPal[i][j] 表示 s[i:j] 是否是回文串。

情况 2：区间不是回文串

这时我们需要将区间分割为两部分，分别删除：

• 枚举分割点 k（i ≤ k < j），将区间分成 s[i:k] 和 s[k+1:j]。
  那么总操作数 = dp[i][k] + dp[k+1][j]。
  取所有分割点的最小值。

情况 3：特殊情况优化

如果 s[i] == s[j]，那么有可能通过先删除内部，让两端字符拼在一起形成回文串，从而减少操作。
例如 s = "abca"，可以先删除 "bc"（操作 1），剩下 "aa" 再删除（操作 1），共 2 次。
我们可以这样考虑：

• 如果 s[i] == s[j]，那么 dp[i][j] 可能等于 dp[i+1][j-1]（当 s[i+1:j-1] 是回文串时，s[i:j] 也是回文串，已由情况 1 覆盖）。
• 但更一般的情况是：s[i] == s[j] 时，dp[i][j] = min(dp[i][j], dp[i+1][j-1])，因为我们可以先删除内部，让两端字符相邻形成更长的回文串，从而减少一次操作。
  但注意：这种转移只在 dp[i+1][j-1] 已经计算过，且两端字符相同时成立。

实际上，更简单的理解是：
如果 s[i] == s[j]，并且 dp[i+1][j-1] 已经是最小删除次数，那么删除 s[i+1:j-1] 后，s[i] 和 s[j] 相邻，它们相同，可以在同一回文删除操作中一起删除。
因此，dp[i][j] 可以取 dp[i+1][j-1]，而不是 dp[i+1][j-1] + 1。

但是，这个逻辑需要小心：
例如 s = "aba"，i=0, j=2，s[i]=s[j]='a'，dp[1][1]=1（删除 'b' 一次），那么删除中间 'b' 后，剩下 "aa" 是一次删除，所以总次数是 1+1=2？不对，因为 "aba" 本身就是回文，一次删除即可。
所以这个例子说明：如果 s[i:j] 已经是回文，直接为 1，不需要分割。

经过分析，正确的状态转移方程如下：

1. 如果 s[i] == s[j] 且区间长度 <= 2，则 dp[i][j] = 1（因为两个相同字符或单字符是回文）。
2. 如果 s[i] == s[j] 且区间长度 > 2，则 dp[i][j] = min(dp[i][j], dp[i+1][j-1])，因为可以先删除内部，然后两端字符一起删除。
3. 对任意区间，枚举分割点 k：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])。

注意：步骤 2 是优化，不是必须，但能减少一些情况的分割。核心还是区间分割。

步骤 4：预处理回文信息

为了快速判断 s[i:j] 是否是回文串，我们可以用动态规划预处理：
isPal[i][j] = (s[i] == s[j]) and (j - i <= 1 or isPal[i+1][j-1])。
如果 isPal[i][j] 为真，则 dp[i][j] = 1。

步骤 5：计算顺序

按区间长度从小到大计算。
最终答案 = dp[0][n-1]。

举例推导

以 s = "abb" 为例，n = 3。

预处理 isPal：

• isPal[0][0]=True, isPal[1][1]=True, isPal[2][2]=True
• isPal[0][1]: s[0]='a', s[1]='b'，不同 → False
• isPal[1][2]: s[1]='b', s[2]='b'，相同 → True
• isPal[0][2]: s[0]='a', s[2]='b'，不同 → False

初始化 dp[i][i] = 1。

长度 2：

• dp[0][1]: 不是回文，枚举 k=0：dp[0][0]+dp[1][1]=1+1=2，所以 dp[0][1]=2。
• dp[1][2]: 是回文（isPal[1][2]=True），所以 dp[1][2]=1。

长度 3：dp[0][2]

• 首先检查是否是回文：isPal[0][2]=False，所以不是 1。
• s[0] != s[2] ('a' != 'b')，所以不能直接用 dp[1][1]。
• 枚举分割点 k：
  • k=0：dp[0][0]+dp[1][2]=1+1=2
  • k=1：dp[0][1]+dp[2][2]=2+1=3
    取最小值 2。

所以 dp[0][2] = 2，答案为 2。

代码实现（伪代码）

n = len(s)
isPal = [[False]*n for _ in range(n)]
for i in range(n):
    isPal[i][i] = True
for length from 2 to n:
    for i from 0 to n-length:
        j = i + length - 1
        if s[i] == s[j] and (length <= 2 or isPal[i+1][j-1]):
            isPal[i][j] = True

dp = [[inf]*n for _ in range(n)]
for i in range(n):
    dp[i][i] = 1

for length from 2 to n:
    for i from 0 to n-length:
        j = i + length - 1
        if isPal[i][j]:
            dp[i][j] = 1
            continue
        if s[i] == s[j]:
            dp[i][j] = min(dp[i][j], dp[i+1][j-1])
        for k from i to j-1:
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

return dp[0][n-1]

复杂度分析

• 时间复杂度：O(n³)，因为有三重循环（区间长度、起点、分割点）。
• 空间复杂度：O(n²)，用于存储 dp 和 isPal 表。

总结

本题是区间动态规划的经典变种，关键在于：

1. 一次操作可以删除一个回文子串，而不是单个字符。
2. 通过预处理回文信息，可以在 O(1) 时间判断区间是否回文。
3. 状态转移时，考虑区间分割和两端字符相同的优化情况。
4. 按区间长度从小到大递推，确保子问题先被解决。

这样，即使字符串长度为 100，O(n³) 也是可行的（1e6 次操作）。