dp[i][j]， i 为 当前的字符数，j为当前字符数中选j个的字符窜的数，因为要去从则用pre记录出现重复的情况
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
dp[0][0] = 1;
dp[i][0] = 1;
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 using ll = long long; 6 constexpr size_t maxn = 1e3 + 5; 7 ll pre[maxn]; 8 ll dp[maxn][maxn]; 9 ll mod = 1e9 + 7; 10 int main() 11 { 12 int n, k; 13 string s; 14 cin >> n >> k>> s; 15 dp[0][0] = 1; 16 s = ' ' + s; 17 for(int i = 1; i <= n; ++ i){ 18 dp[i][0] = 1; 19 for(int j = 1; j <= i; ++ j){ 20 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; 21 if(pre[s[i] - 'a'])dp[i][j] -= dp[pre[s[i] - 'a'] - 1][j-1]; 22 dp[i][j] %= mod; 23 } 24 pre[s[i] - 'a'] = i; 25 } 26 if(dp[n][k] < 0) 27 dp[n][k] += mod; 28 cout << dp[n][k] << endl; 29 30 }