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

  • 思路

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

    • 二维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;
}