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. 重复计数的产生条件与数学证明重复情况出现的充分必要条件有两个字符重复当前字符s[i]在之前位置x出现过s[x] s[i]距离足够近两个相同字符的间距(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 i1; in; i){ int c s[i-1]-a; prePos[i] lastPos[c]; // 记录前一个相同字符位置 lastPos[c] i; // 更新最后出现位置 }3.2 动态规划边界处理需要特别处理几种边界情况当i j时只能删除所有字符方案数为1当j 0时不删除任何字符方案数为1当i j时不可能完成删除方案数为03.3 空间优化技巧虽然题目限定j≤3但通用解法可以只使用两行DP数组滚动计算prev [1]*(k1) # 初始化i0的情况 for i in range(1, n1): curr [0]*(k1) 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 curr4. 完整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 i1; in; i){ int c s[i-1]-a; prePos[i] lastPos[c]; lastPos[c] i; } // 初始化边界条件 dp[0][0] 1; // 空字符串 for(int i1; in; i){ dp[i][0] 1; // 不删除任何字符 for(int j1; j3; 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为最大删除数本题k3空间复杂度O(nk)可通过滚动数组优化到O(k)5. 典型测试用例与调试技巧为了验证代码正确性建议测试以下几类特殊案例测试用例预期结果验证要点a2边界条件aa3重复字符abc7无重复情况aab5部分重复abaca13多重重复调试时最常见的两个错误数组越界prePos数组未初始化导致访问非法内存整数溢出结果可能很大应使用long long类型遇到WA时建议先测试最小案例如长度为1的字符串打印中间DP表检查状态转移是否正确特别检查重复字符处的减法操作是否执行6. 算法扩展与变种思考这道题的通用解法可以处理至多删除k个字符的问题。当k较大时我们可以进行以下优化空间压缩使用两行数组交替计算dp_prev [1]*(k1) for i in range(1, n1): dp_curr [0]*(k1) 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预处理优化对于超长字符串可以分段处理并行计算利用现代CPU的SIMD指令加速DP过程实际比赛中我曾用这个思路解决了LeetCode上类似的Distinct Subsequences II问题。关键在于理解动态规划中的重复计数往往源于相同的字符在不同位置产生相同的子序列效果。