题意：给定一个字符串，求有多少种树与之对应，对应方式是，每次遍历左节点，没有了，就回溯；

 

分析:d[i,j] = sum(d[i+1,k-1],d[k,j]) (str[i]==str[k]);

坑点是数组竟然要long long 不然会超时，神奇；

1 #include 
      
        2  3 using namespace std; 4  5 const int maxn = 300+5; 6 const int mod = 1000000000; 7 char str[maxn]; 8 int d[maxn][maxn]; 9 10 11 int dp(int i,int j) {12     if(i==j) return 1;13     if(str[i]!=str[j]) return 0;14     int& ans = d[i][j];15     if(ans>=0) return ans;16     ans = 0;17 18     for(int k=i+2;k<=j;k++) {19         if(str[i]==str[k]) {20             ans = (ans + (long long)dp(i+1,k-1)*(long long)dp(k,j)) % mod;21         }22     }23     return ans;24 }25 26 int main()27 {28     freopen("exploring.in","r",stdin);29     freopen("exploring.out","w",stdout);30     while(scanf("%s",str)!=EOF) {31         memset(d,-1,sizeof(d));32         printf("%d\n",dp(0,strlen(str)-1));33     }34     return 0;35 }