依旧是《训练指南》上的一道例题。思路大致相同，即设有一个序列S(i),S(i+1),S(i+2)…S(j)，d[i,j]为所求的解。当S(i)==S(k),i<k<=j 时,说明在k回到根，那么S(i+1)…S(k-1)构成一棵独立的子树(当然也可能并不是子树)。那么d[i,j]就要加上d[i+1,k-1]*d[k,j]，不断递增k，每遇到一个k,d[i,j]+=d[i+1,k-1]*d[k,j]直到k>j。最后的d[i,j]就是序列S(i)..S(j)的解。那么题目最终的解即为d[0,n-1],n为序列的长度。
不过，在具体的解法上，我和书上的做法不一样。书上使用的是递归，而我使用了从底向下的方法。显然d[i,i]=1，然后采用类似于最优二叉排序树的解法，依次求出j-i=1,j-i=2….j-i=n-1时的d[i,j]的值。最后输出d[0,n-1]即可。
#include <iostream>#include <cstdio>#include <cstring>#include <string>#define MAX 300+5#define MOD 1000000000using namespace std;long long ans[MAX][MAX];int main(){string S;while(cin>>S){int n=S.size();memset(ans,0,sizeof(ans));for(int i=0;i<n;++i) ans[i][i]=1;//单个节点的树都为一种情况for(int i=1;i<n;++i){//两个坐标间的差值for(int j=0;j+i<n;++j){for(int k=1;k<=i;++k){//从j+1遍历到j+iif(S[j]==S[j+k]){ans[j][j+i]+=ans[j+1][j+k-1]*ans[j+k][j+i];ans[j][j+i]%=MOD;}}}}cout<<ans[0][n-1]<<endl;}return 0;}
，留下许多叫知识和情感的东西握在手里。
