CF1152D
http://codeforces.com/contest/1152/problem/D
大意：给你一个n,表示一个长度为2*n的括号序列，对于所有合法的序列，建立字典树，根节点表示的序列为空序列，让你找不同顶点的边有多少个。
例如 n=2, 答案为 3,图中蓝色的边
字典树
不用关系每个节点表示的确切序列，<<>和<><节点往下，边的情况是一样的，因为每条链都是一个合法的序列，他们的长度一样。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3+7;
const int mod = 1e9+7;
int dp[maxn][maxn][2],n; //dp[i][j][k] 表示长度为i，左括号比右括号多j，当前点和父节点有无连线（k）,的方案数
bool vst[maxn][maxn][2];
int dfs(int i,int j,int k)
{
if(j < 0) return -k;//左括号小于右括号不合法 返回 当k=1返回-1，父节点试图连接，但这个节点不合法，父节点方案数就不会+1，抵消了
if(i+j > 2*n) return -k; //括号合法时长度超限
if(i == 2*n && j == 0) return 0; //叶子节点
if(vst[i][j][k]==1) return dp[i][j][k];
vst[i][j][k] = true;
long long tmp = 0;
if(k == 0){ //当前节点和父节点不连线
tmp = max(dfs(i+1,j-1,1)+dfs(i+1,j+1,0) + 1, //如果没法跟子节点连线，+1被抵消
dfs(i+1,j-1,0)+dfs(i+1,j+1,1) + 1);
}else{
tmp = dfs(i+1,j-1,0) + dfs(i+1,j+1,0);
}
return dp[i][j][k] = tmp%mod;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
cout<<dfs(0,0,0)<<endl;
return 0;
}
