【编程题-错题集】abb（动态规划）

本文主要是介绍【编程题-错题集】abb（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客对应题目链接：abb_牛客题霸_牛客网 (nowcoder.com)

一、分析题目

线性 dp + 哈希表

1、状态表示

dp[i]：表示以 i 位置元素为结尾的所有子序列中，有多少个 _xx。

2、返回值

整张 dp 表的和。

3、状态转移方程

更新顺序：

dp[i] = f[x](前)（这里是更新前的 f[x]，且可以不用创建 dp）
f[x](后) = f[x](前) + i - g[x](前)
g[x](后) = g[x](前) + 1

f[26]：更新前：[0, i-1] 区间内有多少个 _x；更新后：[0, i] 区间内有多少个 _x。
g[26]：更新前：[0, i-1] 区间内有多少个 x；更新后：[0, i] 区间内有多少个 x。

二、代码

//值得学习的代码
//写法一
#include <iostream>
using namespace std;typedef long long LL;
const int N = 1e5+10;
char s[N];
LL dp[N];
LL f[26], g[26];int main()
{int n;cin >> n >> s;LL res=0;for(int i=0; i<n; i++){int x=s[i]-'a';dp[i]=f[x];res+=dp[i];f[x]=f[x]+(i-g[x]);g[x]=g[x]+1;}cout << res << endl;return 0;
}//写法二
#include <iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;int n;
char s[N];
LL f[26];
LL g[26];int main()
{cin >> n >> s;LL ret = 0;for(int i = 0; i < n; i++){int x = s[i] - 'a';ret += f[x];f[x] = f[x] + i - g[x];g[x] = g[x] + 1;}cout << ret << endl;return 0;
}