题目链接：https://vjudge.net/problem/UVA-1362
题解：
区间dp
f[ i ][ j ]表示字符串中从 i 到 j 可以构成子树的个数
为了计数不重复，只考虑第一棵子树的位置，枚举划分点k

盗用sdfzyhx的公式
初始化：f[ i ][ i ] = 1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int mod=1e9;
LL f[350][350];
char s[350];
int main()
{
    int len;
    while(~scanf("%s",s+1))
    {
        len=strlen(s+1);
        memset(f,0,sizeof(f));
        for(int i=1;i<=len;i++) f[i][i]=1;
        for(int i=2;i<=len;i++)
            for(int l=1,r;(r=l+i-1)<=len;l++)
            if(s[l]==s[r])
                for(int k=l+2;k<=r;k++)
                    if(s[k]==s[l])
                        (f[l][r]+=(f[l+1][k-1]*f[k][r])%mod)%=mod;
        printf("%lld\n",f[1][len]);
    }
    return 0;
}