题目
题目链接
题解动态规划。
f[i][j]
表示前i个字符中构成PAT中前j个字符构成字符串的个数,其实就是f[i][1]
表示前i个字符构成P的个数,f[i][2]
表示前i个字符构成PA的个数,f[i][3]
表示前i个字符构成PAT的个数。
状态转移,以更新f[i][2]
为例子,如果s[i]==A
,那么前i-1个字符构成P后加上这个A就可以得到PA,这样得到的PA个数为前i-1个字符构成P
的个数,即f[i-1][P]=f[i-1][1]
,这些是新构成的,因为使用了新的字符s[i]
,还有之前就已经构成的PA,这些的个数为f[i-1][PA] = f[i-1][2]
,故前i个字符构成PA的个数
等于前i-1个字符构成P的个数
+前i-1个字符构成PA的个数
=f[i-1][1] + f[i-1][2]
;如果s[i]!=A
,那么不会有新增加的PA,所以f[i][2]=f[i-1][2]
。
初始化,因为当s[i]==P
时,需要计算f[i][1] = 1 + f[i-1][1]
,即前i-1个字符构成空串的个数
+前i-1个字符构成P的个数
,为了方便将f[0][0]
初始化为1后,在递推更新的过程中f[i][0]
都会被设置为1,这样f[i][1]
更新也可以与其他两个通用一个转移方程了。
其实这个题很简单,但是不知道为什么一遇到动态规划就想记录一下。
代码#include
using namespace std;
const int N = 1e5+10, MOD = 1000000007;
int f[N][4]; // 前i个字符构成 空,P,PA,PAT 的个数
map mp = {{'P', 1}, {'A', 2}, {'T', 3}};
string s;
int main()
{
cin >> s;
int n = s.size();
s = '.' + s;
f[0][0] = 1;
for (int i = 1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?