DP
先不考虑重复
dp[i][j]表示到i位置已经删了j个的种类数
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
如果只是这样转移肯定会有重复的。例如一个字符串cdabnaxy，你删除abn和删除bna后得到的字符串都是cdaxy。
这时候就要去重了，根据上面那个栗子可以发现对于一个字符s[i]，如果在i之前存在一个x使得s[x]=s[i]，那么删除[x,i-1]间的字符 和删除[x+1,i]间的字符其实是重复的，等价的，那么d[i][j]就要减去d[x-1][j-(i-x)]，减去删除这段造成的重复串。
参考：https://blog.csdn.net/Mitsuha_/article/details/81123057
#include <bits/stdc++.h>
using namespace std;
#define MOD (int)(1e9+7)
#define ll long long
#define db(a) (cout<<"->"<<a<<endl)
#define FORP(i,a,b) for(int i=a;i<=b;++i)
ll pre[1002000];
ll dp[1020000][5];
int main(){string s;cin>>s;ll len=s.size();s='#'+s;dp[0][0]=1;FORP(i,1,len){FORP(j,0,2){dp[i][j]=dp[i-1][j-1]+dp[i-1][j];//不考虑重复的转移for(int k=i-1;k>=1&&(i-k)<=j;--k){if(s[k]==s[i]){dp[i][j]-=dp[k-1][j-(i-k)];break;}}}}cout<<dp[len][0]+dp[len][1]+dp[len][2]<<endl;return 0;
}