题目（来自PTA，没有测试平台）

给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？

输入格式：
输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 10^6] 内的字符串。

输出格式：
在一行中输出至多删掉其中 3 个字符后不同字符串的个数。

输入样例：
ababcc
输出样例：
25
提示：

删掉 0 个字符得到 "ababcc"。

删掉 1 个字符得到 "babcc", "aabcc", "abbcc", "abacc" 和 "ababc"。

删掉 2 个字符得到 "abcc", "bbcc", "bacc", "babc", "aacc", "aabc", "abbc", "abac" 和 "abab"。

删掉 3 个字符得到 "abc", "bcc", "acc", "bbc", "bac", "bab", "aac", "aab", "abb" 和 "aba"。

解题思路

dp。
dp[i][j]表示前i个字符，删除j个字符，得到的不同字符串的数目。
假如所有字符都不相同，那么删除j个字符后得到的不同字符串的数目为dp[i-1][j]+dp[i-1][j]，含义为对于第i个字符，我们可以不选它，也可以选它。
但是存在重复的情况，此时dp[i][j]-=dp[k-1][j-(i-k)]。
含义为，我们将区间[k,i-1]的字符删去与将区间[k+1,i]的字符删去，最终得到的字符串相同，这属于重复的情况，我们需要删去重复的情况。
如何判断是否存在重复？
当存在是s[k]=s[i]时，说明前i个字符要删除j个字符，而此时删去区间[k,i-1]与删除区间[k+1,i]得到的字符串相同，就要减去重复的情况，即前k-1个字符删去j-(i-k)个字符是重复的。

AC代码

#include<bits/stdc++.h>
#define ll long long//开ll 
using namespace std;
const int N=1e6+10;
ll dp[N][4];
string str;
int main(){
    cin>>str;
    int n=str.size();
    str='.'+str;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=3;j++){
            if(j==0) dp[i][j]=1;
            else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            for(int k=i-1;j>=(i-k) && k>=1;k--){
                if(str[i]==str[k]) {
                    dp[i][j]-=dp[k-1][j-(i-k)];
                    break;
                }
            }        
        }
    }
    cout<<dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3]<<endl;
}