PTA L3-020算法题保姆级攻略：动态规划解决‘至多删三个字符’的重复计数难题

第一次遇到这道题时，我盯着屏幕上的"abcac"样例陷入了沉思——为什么简单的状态转移方程会漏算重复情况？这个问题困扰了我整整三个晚上。直到某次洗澡时突然灵光一现，才明白关键在于处理字符重复时的特殊状态转移。本文将用最直观的方式，带你彻底攻克这个算法竞赛中的经典陷阱。

1. 问题本质与基础DP模型

题目要求计算给定字符串在删除0到3个字符后能形成的不同子串数量。初学者最容易想到的解法是暴力枚举所有可能的删除组合，但这种方法对长度为n的字符串时间复杂度高达O(n^3)，显然无法通过大规模测试用例。

动态规划之所以适合此题，是因为它能够将复杂问题分解为重叠子问题。我们定义：

• dp[i][j]：前i个字符中删除j个字符形成的不同子串数

初始状态转移方程看似简单：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
# 不删s[i]  删s[i]

但实际测试样例"abcac"时会发现：

• 删除第4、5个字符("ac")得到"abc"
• 删除第2、4个字符("b","a")也得到"abc"
• 删除第2、5个字符("b","c")还是得到"abc"

这就是典型的重复计数问题，直接套用基础方程会导致结果偏大。

2. 重复计数的产生条件与数学证明

重复情况出现的充分必要条件有两个：

1. 字符重复：当前字符s[i]在之前位置x出现过（s[x] == s[i]）
2. 距离足够近：两个相同字符的间距(i-x) ≤ 可删除数j

用数学语言表述就是： 当存在x < i使得s[x] == s[i]且i-x ≤ j时，需要减去重复计数dp[x-1][j-(i-x)]

为什么是这个公式？ 让我们拆解这个看似复杂的表达式：

假设字符串形如"...a...a"，其中第一个a在位置x，第二个在i。要产生重复的子串，必须满足：

• 不删除s[i]时：保留第二个a，前面删除j个字符
• 删除s[i]时：需要删除第二个a和中间的(i-x-1)个字符，再在前x个字符中删除剩余的j-(i-x)个

只有当这两种操作可能产生相同子串时，才需要减去重复计数。而重复的数量正好等于前x-1个字符删除j-(i-x)个字符的方案数。

3. 优化实现的关键技巧

实际编码时需要特别注意三个优化点：

3.1 预处理字符位置

使用长度为26的数组记录每个字母最后出现的位置：

int lastPos[26] = {0};
for(int i=1; i<=n; i++){
    int c = s[i-1]-'a';
    prePos[i] = lastPos[c]; // 记录前一个相同字符位置
    lastPos[c] = i; // 更新最后出现位置
}

3.2 动态规划边界处理

需要特别处理几种边界情况：

1. 当i == j时：只能删除所有字符，方案数为1
2. 当j == 0时：不删除任何字符，方案数为1
3. 当i < j时：不可能完成删除，方案数为0

3.3 空间优化技巧

虽然题目限定j≤3，但通用解法可以只使用两行DP数组滚动计算：

prev = [1]*(k+1)  # 初始化i=0的情况
for i in range(1, n+1):
    curr = [0]*(k+1)
    for j in range(min(i,k)+1):
        if j == 0:
            curr[j] = 1
        else:
            curr[j] = prev[j] + prev[j-1]
            x = prePos[i]
            if x and i-x <= j:
                curr[j] -= dp[x-1][j-(i-x)]
    prev = curr

4. 完整AC代码与逐行解析

以下是带详细注释的C++实现，重点解释了重复计数的处理逻辑：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[1000005][4]; // dp[i][j]表示前i个删j个
int prePos[1000005]; // 记录前一个相同字符位置

int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    // 预处理每个字符前一个相同字符的位置
    int lastPos[26] = {0};
    for(int i=1; i<=n; i++){
        int c = s[i-1]-'a';
        prePos[i] = lastPos[c];
        lastPos[c] = i;
    }
    
    // 初始化边界条件
    dp[0][0] = 1; // 空字符串
    for(int i=1; i<=n; i++){
        dp[i][0] = 1; // 不删除任何字符
        for(int j=1; j<=3; j++){
            if(i == j) dp[i][j] = 1;
            else if(i < j) dp[i][j] = 0;
            else {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                int x = prePos[i];
                if(x && i-x <= j){ // 存在重复计数条件
                    dp[i][j] -= dp[x-1][j-(i-x)];
                }
            }
        }
    }
    
    cout << dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3];
    return 0;
}

复杂度分析：

• 时间复杂度：O(nk)，其中k为最大删除数（本题k=3）
• 空间复杂度：O(nk)，可通过滚动数组优化到O(k)

5. 典型测试用例与调试技巧

为了验证代码正确性，建议测试以下几类特殊案例：

测试用例	预期结果	验证要点
"a"	2	边界条件
"aa"	3	重复字符
"abc"	7	无重复情况
"aab"	5	部分重复
"abaca"	13	多重重复

调试时最常见的两个错误：

1. 数组越界：prePos数组未初始化导致访问非法内存
2. 整数溢出：结果可能很大，应使用long long类型

遇到WA时建议：

1. 先测试最小案例（如长度为1的字符串）
2. 打印中间DP表检查状态转移是否正确
3. 特别检查重复字符处的减法操作是否执行

6. 算法扩展与变种思考

这道题的通用解法可以处理"至多删除k个字符"的问题。当k较大时，我们可以进行以下优化：

1. 空间压缩：使用两行数组交替计算

dp_prev = [1]*(k+1)
for i in range(1, n+1):
    dp_curr = [0]*(k+1)
    dp_curr[0] = 1
    for j in range(1, min(i,k)+1):
        dp_curr[j] = dp_prev[j] + dp_prev[j-1]
        # ...重复计数处理...
    dp_prev = dp_curr

2. 预处理优化：对于超长字符串，可以分段处理

3. 并行计算：利用现代CPU的SIMD指令加速DP过程

实际比赛中，我曾用这个思路解决了LeetCode上类似的"Distinct Subsequences II"问题。关键在于理解：动态规划中的重复计数往往源于相同的字符在不同位置产生相同的子序列效果。