本文共 1021 字，大约阅读时间需要 3 分钟。

关键词：递推关系,动态规划

备注：

解决方案：

#include
   
    #include
    
     using namespace std;const int maxn=100010;const int mod=1000000007;//算法笔记思路：寻找每一个A左边的P的个数和右边的T的个数int main(){       char str[maxn];    int leftP[maxn]={   0};    int ans=0,rightT=0;    //获取输入字符串    cin>>str;    int len=strlen(str);    for(int i=0;i
     
      =0;i--){    //从右向左遍历字符串        //当前字符为T则计数+1        if(str[i]=='T'){               rightT++;        //当前字符为A则左边P数与右边T数相乘得到当前A可组成pat的结果        }else if(str[i]=='A'){                ans=(ans+leftP[i]*rightT)%mod;//每次都要取余，否则可能溢出        }    }    cout<
     
    
   

代码简化：

#include
   
    #include
    
     using namespace std;const int maxn=100010;const int mod=1000000007;//参考大佬简练的代码int main(){       char str[maxn];    int p=0,pa=0,pat=0;    //获取输入字符串    cin>>str;    int len=strlen(str);    for(int i=0;i