本文共 1408 字，大约阅读时间需要 4 分钟。

1、

2、题目大意：

给定一个字符串，求出该字符串有多少个不同的子序列

定义dp[k]为前k个字符中子序列的个数

那么dp[k]来自于两种状态，

dp[k]=2*dp[k-1]+1;如果a[k]与前k-1个字符都不相同

dp[k]=2*dp[k-1]-dp[t-1],如果a[k]与前k-1个字符有相同的，t是与之相同的最近的一个下标

3、题目：

Problem 2129 子序列个数

四、AC代码：

#include
   
    #include
    
     #define N 1000005#define mod 1000000007#define ll long longint a[N],b[N];ll dp[N];int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        int maxx=-1;        for(int i=1; i<=n; i++)        {            scanf("%d",&a[i]);            if(a[i]>maxx)                maxx=a[i];        }        for(int i=0; i<=maxx; i++)            b[i]=-1;        b[a[1]]=1;        dp[1]=1;        for(int i=2; i<=n; i++)        {            if(b[a[i]]==-1)                dp[i]=(2*dp[i-1]+1)%mod;            else                dp[i]=(2*dp[i-1]-dp[b[a[i]]-1]+mod)%mod;//如出现负值，处理            b[a[i]]=i;        }        printf("%lld\n",dp[n]%mod);    }    return 0;}
    
   

转载地址：http://ghddi.baihongyu.com/