题目：金字塔
网址：http://noi-test.zzstep.com/contest/0x50「动态规划」例题/5302 金字塔
描述
虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。
经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。
首先，金字塔由若干房间组成，房间之间连有通道。
如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。
并且，每个房间的墙壁都涂有若干种颜色的一种。
探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。
这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。
机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。
最后，机器人会从入口退出金字塔。
显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。
但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。
现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。
因为结果可能会非常大，你只需要输出答案对(10^9) 取模之后的值。
输入格式
输入仅一行，包含一个字符串S，长度不超过(300)，表示机器人得到的颜色序列。
输出格式
输出一个整数表示答案。
输入样例：
ABABABA
输出样例：
5
这道题看似一道区间DP，但它包含着树分治的思想。
具体来说，什么是树分治呢？其实就是说，对于一个操作，它只允许两棵树之间进行，对于多棵树便略显吃力了。那么此时，我们先从最左端的开始，一颗一颗地合并，最终完成了树上的操作。
不难想到定义(dp[i, j])代表序列([i, j])构成的不同的树的个数。
这道题，对于一个序列而言，构成子树的充要条件为：序列左右字符一样。
显然，如果不一样，dp值为0（因为它不可能是一颗完整的树啊）。
那么，对于可以构成的子树而言，该如何转移呢？这时候，树分治的思想便有作用。
我们只考虑第一棵子树，枚举第一棵子树的序列，剩下的交给后面的了。事实上，我们可以这样理解：找到k，用(dp[i + 1, k - 1] * dp[k, j])来更新答案。
为什么这是对的？换句话说，为什么不是用(dp[i + 1, k - 1] * dp[k, j - 1])，那是因为枚举的(k)必须要保证是这棵子树的根节点。换言之，k这位的字符一定要与j的字符保持一致。
初始化：(dp[i, i] = 1)，其余均为0即可！
当然这道题本身比较贴近树形DP，采取记忆化搜索也很自然。
递推代码如下：
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int maxn = 300 + 5, mod = 1e9;
int n;
long long dp[maxn][maxn];
string S;
int main()
{
cin >> S;
n = S.size();
for(int i = 0; i < n; ++ i) dp[i][i] = 1;
for(int len = 3; len <= n; ++ len)
{
for(int i = 0, j = len - 1; j < n; ++ i, ++ j)
{
if(S[i] != S[j]) continue;
for(int k = i + 2; k <= j; ++ k)
{
dp[i][j] = (dp[i][j] + dp[i + 1][k - 1] * dp[k][j]) % mod;
}
}
}
printf("%d
", dp[0][n - 1] % mod);
return 0;
}
记忆化搜索代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
const int maxn = 300 + 5, mod = 1e9;
int n;
long long dp[maxn][maxn];
string S;
long long dfs(int l, int r)
{
if(dp[l][r] != -1) return dp[l][r];
long long &ans = dp[l][r];
ans = 0;
if(l > r || S[l] != S[r]) return ans;
if(l == r) return ans = 1;
for(int k = l + 2; k <= r; ++ k)
{
ans = (ans + dfs(l + 1, k - 1) * dfs(k, r)) % mod;
}
return ans;
}
int main()
{
cin >> S;
n = S.size();
memset(dp, -1, sizeof(dp));
printf("%d
", dfs(0, n - 1));
return 0;
}