---

动态规划专题(PAT)：

1.PAT计数

PAT计数

 

2.快速排序

快速排序

 

3.最大子序列和

最大子序列和

 

4.最佳彩色带

最佳彩色带

 

5.找更多硬币

找更多硬币

 

AC代码：

1.PAT计数

/*
  dp[i][1]: [1,i]中"P"的数量
  dp[i][2]: [1,i]中"PA"的数量
  dp[i][3]: [1,i]中"PAT"的数量
  
  dp[i][j]: 所有子串分为两部分,一部分是以s[i]结尾的子串,一部分是其他
  = dp[i - 1][j] + dp[i - 1][j - 1]
*/
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1000000007;
string s;
string pat = "#PAT";
ll dp[N][5];

int main (void){
  memset(dp,0,sizeof dp);
  cin >> s;
  
  if (s[0] == 'P') dp[0][1] = 1; // 边界特判
  for (int i = 0; i < s.size(); ++i) dp[i][0] = 1;
  
  for (int i = 1; i < s.size(); ++i){
    for (int j = 1; j <= 3; ++j){
      dp[i][j] = dp[i - 1][j];
      
      if (s[i] == pat[j]) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
    }
  }
  
  cout << dp[s.size() - 1][3] << endl;
  
  return 0;
}

...