C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 310, mod = 1e9;

string s;
ll memo[N][N];

int solve(int l, int r){
    if(l == r) return 1;
    if(l > r) return 0;
    if(memo[l][r] != -1) return memo[l][r];
    memo[l][r] = 0;
    for(int k = l + 2;k <= r;++k)//枚举第一棵子树在s中划分的结束位置
        if(s[k] == s[l])
            memo[l][r] = (memo[l][r] + (ll)solve(l+1, k-1)*solve(k, r)) % mod;
    return memo[l][r];
}

int main(){
    cin >> s;
    memset(memo, -1, sizeof memo);
    cout << solve(0, s.size()-1) << endl;
}