题目链接：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;
}