1 /* 2 把一个字符串分成若干段，每一段里面的字符不能重复，问有多少种分法 3 动态规划，定义dp 表示字符串前n个字母的分法种数，先预处理字符串，对于每个字符， 4 计算出以这个字符为结尾的无重复字符的一段最长的长度，第i个字符对应的长度记为f[i] 5 然后可以得出递推式： 6 dp[0]=1; 7 dp[i]=dp(i-j) (1<=j<=f[i]) 8 */ 9 #include 
     
      10 using namespace std;11 int dp[10005];12 int f[10005];13 bool vis[10];14 const int mod=1e9+7;15 int main()16 {17     string s;18     int n;19     cin>>n>>s;20     memset(dp,0,sizeof(dp));21     memset(f,0,sizeof(f));22     for(int i=0;i
      
       =0;j--)27         {28             if(vis[s[j]-'0'])29                 break;30             cnt++;31             vis[s[j]-'0']=1;32         }33         f[i+1]=cnt;34     }35     dp[0]=1;36     for(int i=1;i<=n;i++)37     {38         int sum=0;39         for(int j=1;j<=f[i];j++)40         {41             sum=(sum+dp[i-j])%mod;42         }43         dp[i]=sum;44     }45     cout<
       
        <