由于进入一棵子树以及从一棵子树中出去,都需要遍历根节点,根据这个性质,很容易想到判断左端点和右端点是否相同,进而考虑状态的转移,把一棵树分成一棵子树以及其它子树,从小状态滚到大状态。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=305,mod=1e9;
int f[N][N];char s[N];
int main()
{
    scanf("%s",s+1);int n=strlen(s+1);memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)f[i][i]=1;
    for(int k=3;k<=n;k++)
        for(int l=1;l<=n-k+1;l++)
        {
            int r=l+k-1;
            if(s[l]==s[r])
            {
                f[l][r]=f[l+1][r-1];//只有一棵子树的情况。 
                for(int mid=l+2;mid<=r-2;mid++)
                    f[l][r]=(f[l][r]+1ll*f[l+1][mid-1]*f[mid][r]%mod)%mod;//f[l][r]构成一棵树,枚举其第一棵子树(包含子树的根),其余组成剩余的部分(其他子树以及树的根节点)(若f[mid][r]有值,说明s[mid]==s[r],相当于一个子问题的f[l][r],也就可以说明mid是回到了根结点的。)  
            }
        }
    printf("%d\n",f[1][n]);
    return 0;
}