[PAT*]1025 Keep at Most 100 Characters (35分)

分析：

dp[i][j]表示考虑前i位，能够得到的长度为j的串的数量，
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
dp[i - 1][j - 1]代表了以s[i]结尾的长度为j的个数，显然跟dp[i - 1][j]有重合的部分，也就是dp[i - 1][j]中以s[i]结尾的长度为j的个数，所以只需要把这部分扣除就可,用last[]记录s[i]最近出现的位置。
初始化：每次初始化dp[i][1] = dp[i - 1][1] + !(s[i]之前是否出现过)

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
ll dp[1010][110];
int last[30];

int main()
{
    char s[1010]; cin >> (s + 1);
    int n = strlen(s + 1);
    for(int i = 1; i <= n; i++)
    {
        int pos = last[s[i] - 'a'];
        dp[i][1] = dp[i - 1][1] + !pos;
        for(int j = 2; j <= min(i, 100); j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - (pos ? dp[pos - 1][j - 1] : 0);
            dp[i][j] = (dp[i][j] % mod + mod) % mod;
        }
        last[s[i] - 'a'] = i;
    }
    ll res = 0;
    for(int i = 1; i <= min(n, 100); i++)
        res = (res + dp[n][i]) % mod;
    cout << res << endl;

}

本文地址：https://blog.csdn.net/weixin_43987810/article/details/107531233