【牛客练习赛60：C】操作集锦（dp+子序列计数）

题目
给出长度为的字符串，求有多少种不同的长度为的子序列。

思路

• 空串也是一种合法的子序列，所以特判

• 二维dp求解(当然也可以一维，我原本的做法是一维的，比下面的解法稍微麻烦一点，就不讲啦)

  • 解法一：
    表示前个字符中长度为且以为结尾的子序列种类数
    表示后面第一次出现的位置，这样做是为了避免重复统计答案。
    转移方程：

       
    
    注意初始化：

  • 解法二：
    表示前个字符中长度为的子序列种类数
    表示上一次出现的位置
    转移方程：
    注意为了防止dp[i][j]的结果为负数，需要+mod再取模

    

    注意初始化

ac代码：

• 解法一：

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const ll mod = 1e9+7;
  const int maxn = 1e3+10;
  ll dp[maxn][maxn];
  int nxt[maxn][30];
  int n, k;
  char s[maxn];
  int main()
  {
  scanf("%d %d", &n, &k);
  scanf("%s", s+1);
  if(k==0) {printf("1\n"); return 0;}
  for(int i = 0; i < n; i++)
    for(int j = i+1; j <= n; j++)
        if(!nxt[i][s[j]-'a']) nxt[i][s[j]-'a'] = j;
  dp[0][0] = 1;
  for(int i = 0; i <= n; i++)
  {
    for(int j = 0; j <= min(i, k); j++)
    {
        for(int p = 0; p < 26; p++)
        {
            int x = nxt[i][p];
            if(x!=0) dp[x][j+1] = (dp[x][j+1]+dp[i][j])%mod;
        }
    }
  }
  ll ans = 0;
  for(int i = k; i <= n; i++) ans = (ans+dp[i][k])%mod;
  printf("%lld\n", ans);
  return 0;
  }

• 解法二：

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const ll mod = 1e9+7;
  const int maxn = 1e3+10;
  ll dp[maxn][maxn];
  int last[maxn];
  int n, k;
  char s[maxn];
  int main()
  {
  scanf("%d %d", &n, &k);
  scanf("%s", s+1);
  if(k==0) {printf("1\n"); return 0;}
  dp[0][0] = 1;
  for(int i = 1; i <= n; i++)
  {
    dp[i][0] = 1;
    for(int j = 1; j <= min(i, k); j++)
    {
        dp[i][j] = (dp[i-1][j]+dp[i-1][j-1])%mod;
        if(last[s[i]-'a']!=0) dp[i][j] = (dp[i][j]-dp[last[s[i]-'a']-1][j-1]+mod)%mod;
    }
    last[s[i]-'a'] = i;
  }
  printf("%lld\n", dp[n][k]%mod);
  return 0;
  }