题意：给出一个字符串。问有多少个满足以下条件的树
从原点开始尽可能左走，不行就回溯，其路径符合给出字符串。
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> #include <math.h> using namespace std; typedef long long LL; const LL mod = 1000000000; const LL maxn = 300 + 10; LL dp[maxn][maxn]; char s[maxn]; LL gao(LL i, LL j) { if (~dp[i][j]) return dp[i][j]; if (i == j) return dp[i][j] = 1; if (s[i] != s[j]) return dp[i][j] = 0; LL ans = 0; for (LL x = i + 2; x <= j; x++){ if (s[i] != s[x]) continue; ans += gao(i + 1, x - 1) * gao(x, j); ans %= mod; } return dp[i][j] = ans; } int main() { while (cin >> s){ LL len = strlen(s); memset(dp, -1, sizeof(dp)); cout << gao(0, len - 1)<<endl; } return 0; }
原文：http://www.cnblogs.com/yigexigua/p/4018407.html