分析

设 为字符串中从 到 部分为一整棵树时的方案数。那么考虑子树的划分，那么 ，考虑子树在 处回到根节点。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9,N = 310;
char ch[N];int f[N][N],n;
int main() {
    scanf("%s",ch + 1);n = strlen(ch + 1);
    for(int i = 1;i <= n;i++) f[i][i] = 1;
    for(int len = 2;len <= n;len++) {
        for(int i = 1;i + len - 1 <= n;i++) {
            int j = i + len - 1;
            if(ch[i] == ch[j]) {
                for(int k = i + 1;k < j;k++) {
                    if(ch[k - 1] == ch[i]) 
                    f[i][j] = (f[i][j] + 1ll * f[i][k - 1] * f[k][j - 1] % mod) % mod;
                }                
            }
        }
    }
    cout << f[1][n] << endl;return 0;
}