描述

给一个长度为$nn$的字符串，问有多少个形式为abb的子序列

思路

• 一个比较常见的动态规划题目，设$dp[i][j]dp[i][j]$表示区间$[1,i][1,i]$中以字母$jj$为结尾，有多少个形式为ab的子序列，则对于字符串$ss$最终的答案为${\sum }_{i\in [1,n]}dp[i-1][s[i]]\backslash sum\_\{i\; \backslash in\; [1,n]\}\{dp[i-1][s[i]]\}$，同时,，$cnt[j]cnt[j]$为区间$[1,i-1][1,i-1]$中字母$jj$出现的次数。

• 由于更新$dp[i][s[i]]dp[i][s[i]]$仅和$i-1i-1$的各个状态相关，因此可以边循环变$dpdp$，可以省略一维存储空间

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
int cnt[30];
ll dp[MAXN];
char s[MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        int& num=cnt[s[i]-'a'];
        int tot=i-1-num;
        sum+=dp[s[i]-'a'];
        dp[s[i]-'a']+=tot;
        num++;
    }
    printf("%lld\n",sum);
}

时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$