原题链接
思路：
d p [ i ] [ j ]表示枚举到第i位时，删除了j个得到的不同的字符串个数。
转移的时候考虑第i ii位是否被删除：
dp[i][j]=dp[i−1][j]+dp[i−1][j−1]
这样没有去掉重复的情况，什么情况才会导致重复计数呢。
比如a b a b c c，枚举到第4位的时候，删除两个字符a b，得到字符串位a b cc，但是到第3位的时候删除两个字符也会得到这个字符串，这就导致了重复。
从当前枚举的位置i ii往前看，因为后面的字符还没有开始删除，不会造成影响。
如果s [ i ] = = s [ k ]说明删除[ k , i − 1 ]和[ k + 1 , i ]得到的字符串是相同的，将前面的贡献减掉即可。
找到一个退出即可，因为是从左往右枚举的，前面不合法的已经去掉了。
代码：
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=1e6+7; ll res,dp[maxn][4]; char s[maxn]; int main(){ cin>>s+1; int n=strlen(s+1); dp[0][0]=1; ///dp[i][j]表示到第i位时 删除了j位 得到的字符串个数 for(int i=1;i<=n;i++){ for(int j=0;j<=3;j++){ dp[i][j]=(dp[i][j]+dp[i-1][j]); if(j>=1) dp[i][j]=(dp[i][j]+dp[i-1][j-1]); for(int k=i-1;k>=i-j;k--) if(s[i]==s[k]){ dp[i][j]-=dp[k-1][j-(i-k)]; break; } } } ll res=0; for(int i=0;i<4;i++) res+=dp[n][i]; cout<<res<<endl; return 0; }
