https://ac.nowcoder.com/acm/contest/4853/C
求长度为n的字符串的 长度为k的不同子序列。
dp[i][j]表示前i个字符串，长度为j的子序列数量。
不计算重复，对于第j个字符，dp[i][j]=dp[i-1][j]+dp[i-1]+dp[j-1];前者不用上第j个字符，后者用上第j个字符。
去重，对于当前字符x，last[x]表示上一次x出现的位置，去重部分dp[ pre[x]-1 ][j-1]。
这个去重理解了挺久，纸上比划一下才清楚,例如有字符串abcdde(下标1-6),j=2
i=4时，x=d，dp[4][2]=dp[3][2]+dp[3][1];
i=5时，x=d，dp[5][2]=dp[4][2]+dp[4][1]-dp[3][1];
上一个d在i=4的位置，需要把 用i=4的d 的情况 去掉，也就是dp[3][1]。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<ctime> #define ll long long #define inf 0x3f3f3f3f const double pi=3.1415926; const double eps=1e-9; const ll p=1e9+7; using namespace std; ll dp[1005][1005]; ll last[30]; char a[1005]; int n,k; int main() { scanf("%d %d",&n,&k); getchar(); scanf("%s",a+1); dp[0][0]=1; for(int i=1;i<=n;i++) { int x=a[i]-'a'; dp[i][0]=1; for(int j=1;j<=i;j++) { dp[i][j]=dp[i-1][j]+dp[i-1][j-1]; if(last[x]!=0) dp[i][j]-=dp[ last[x]-1 ][j-1]; dp[i][j]=dp[i][j]%p; } last[x]=i; } if(dp[n][k]<0) dp[n][k]+=p;///坑 printf("%lld ",dp[n][k]); return 0; }