最长回文子序列的变种：带字符删除限制的最长回文子序列（允许删除至多k个字符）

题目描述

给定一个字符串 s 和一个整数 k，你可以从字符串中删除最多 k 个字符（可以不删除），求删除后能形成的最长回文子序列的长度。

示例：

• 输入：s = "abca", k = 1
• 输出：3
• 解释：删除 'c' 得到 "aba"，最长回文子序列长度为 3。

注意：

• 子序列不一定连续，但要保持相对顺序。
• 只允许删除字符，不能插入或替换。
• 删除的字符总数不能超过 k。

解题思路

这个问题是“最长回文子序列”的扩展，额外允许删除至多 k 个字符。我们可以用动态规划来逐步求解。

1. 状态定义

设 dp[i][j][d] 表示在子串 s[i..j] 中，最多删除 d 个字符时，能得到的最长回文子序列的长度。

• i 和 j 是子串的左右端点（0 ≤ i ≤ j < n）。
• d 表示在子串 s[i..j] 中最多可删除的字符数量（0 ≤ d ≤ k）。

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

2. 状态转移分析

考虑子串 s[i..j]：

1. 如果 s[i] == s[j]：

   • 可以同时选择 s[i] 和 s[j] 作为回文的两端，此时不需要删除它们，长度加 2，然后递归到子串 s[i+1..j-1]，删除限制仍为 d。

     dp[i][j][d] = dp[i+1][j-1][d] + 2
     

   • 注意：如果 i == j，则长度为 1，即 dp[i][j][d] = 1。
   • 如果 i+1 > j-1（即子串长度 ≤ 2 且两端相等），则长度为 2 或 1，取决于是否 i == j。

2. 如果 s[i] != s[j]：
   有三种选择：

   • 删除 s[i]，然后尝试在 s[i+1..j] 中找最长回文子序列，此时删除次数减少 1（即 d-1，但需保证 d-1 ≥ 0）：

     dp[i][j][d] = dp[i+1][j][d-1]   （如果 d > 0）
     

   • 删除 s[j]，在 s[i..j-1] 中找，删除次数减少 1：

     dp[i][j][d] = dp[i][j-1][d-1]   （如果 d > 0）
     

   • 既不删除 s[i] 也不删除 s[j]，但此时不能将它们同时纳入回文，只能分别在 s[i+1..j] 和 s[i..j-1] 中找，但删除次数不减少，取较大值：

     dp[i][j][d] = max(dp[i+1][j][d], dp[i][j-1][d])
     

   注意：当 d > 0 时，前两种删除操作是可行的；而第三种总是可行的。所以实际上我们可以合并为：

   dp[i][j][d] = max(dp[i+1][j][d], dp[i][j-1][d])
   if d > 0:
       dp[i][j][d] = max(dp[i][j][d], dp[i+1][j][d-1], dp[i][j-1][d-1])
   

   但要小心重复比较，更清晰的写法是下面实现时的逻辑。

3. 边界情况：

   • 当 i > j 时，子串为空，长度为 0。
   • 当 i == j 时，长度为 1。

3. 动态规划递推顺序

因为 dp[i][j][d] 依赖于 i+1 和 j-1，所以 i 从大到小（从 n-1 到 0），j 从小到大（但保证 j ≥ i），d 从 0 到 k 任意顺序均可。

4. 实现细节（伪代码）

n = len(s)
初始化 dp[n][n][k+1] 为 0
for i in [0, n-1]:
    for d in [0, k]:
        dp[i][i][d] = 1  # 单个字符是回文

for length from 2 to n:  # 子串长度
    for i in [0, n-length]:
        j = i + length - 1
        for d in [0, k]:
            if s[i] == s[j]:
                if i+1 <= j-1:
                    dp[i][j][d] = dp[i+1][j-1][d] + 2
                else:  # i+1 > j-1 即 length=2
                    dp[i][j][d] = 2
            else:
                # 不删除 i 或 j
                dp[i][j][d] = max(dp[i+1][j][d], dp[i][j-1][d])
                if d > 0:
                    # 删除 i
                    dp[i][j][d] = max(dp[i][j][d], dp[i+1][j][d-1])
                    # 删除 j
                    dp[i][j][d] = max(dp[i][j][d], dp[i][j-1][d-1])
return dp[0][n-1][k]

5. 示例推演（s = "abca", k = 1）

n=4，k=1。

初始化长度 1 子串：
dp[i][i][d] = 1 对所有 d。

长度 2：

• i=0, j=1: s[0]='a', s[1]='b' 不相等
  d=0: 不删除 → max(dp[1][1][0], dp[0][0][0]) = 1
  d=1: 不删除得 1；删除'a' → dp[1][1][0]=1；删除'b' → dp[0][0][0]=1 → 结果 1
• i=1, j=2: 'b','c' → 类似得 1
• i=2, j=3: 'c','a' → 1

长度 3：

• i=0, j=2: 'a','c' 不相等
  d=0: max(dp[1][2][0], dp[0][1][0]) = max(1,1)=1
  d=1: 不删除得 1；删除'a'→dp[1][2][0]=1；删除'c'→dp[0][1][0]=1 → 1
• i=1, j=3: 'b','a' 不相等，类似得 1

长度 4：i=0, j=3: 'a','a' 相等
d=0: 不删除 → dp[1][2][0]+2 = 1+2=3
d=1: 相等 → dp[1][2][1]+2 = 1+2=3

最终 dp[0][3][1] = 3。

6. 时间与空间复杂度

• 时间复杂度：O(n² × k)
• 空间复杂度：O(n² × k)，可优化为 O(n × k) 的滚动数组（但实现较复杂）。

7. 小结

这个问题将最长回文子序列扩展为可删除字符，增加了“删除预算”维度。
状态转移时要考虑：两端相等时直接加 2，不等时可删除左、删除右，或不删除两端但分别缩小区间。
最终答案是 dp[0][n-1][k]，表示整个字符串在最多删除 k 个字符时的最长回文子序列长度。