有一棵有根树，第i个点上带有字符(c_i)，现在给出这个树关于其字符的dfs序s，现在求这棵树的方案数，dfs序长度n不超过300.
解
实际上dfs序本身具有区间性，因此可以考虑区间dp，于是设(dp[i][j])表示dfs序的区间([i,j])的一棵有根树的方案数，考虑dfs序的性质，必然该树的根节点把序列划分成了几棵子树，于是我们可以枚举根节点的位置，但是时间复杂度太高。
如果按照常用思路考虑把区间划分成两个部分，每个部分包含若干个子树，这样显然会有重复部分被计算，原因在于新枚举的区间包含了旧区间的方案，因此要设法独立两者。
因此考虑枚举其中第一棵子树的区间，剩下的子树连同根节点组成一棵树，这样就不会存在重复，于是我们有
[dp[i][j]=sum_{k=i+2}^jdp[i+1][k-1] imes dp[k][j]
]
边界：(dp[i][i]=1,i=1,2,3.,,,n)，其余为0
答案：(dp[1][n])
参考代码：
阶段实现：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
#define yyb 1000000000
using namespace std;
string s;
ll dp[301][301];
int main(){
cin>>s;
for(int i(1);i<=s.size();++i)dp[i][i]=1;
for(int i,j(1),k;j<=s.size();++j)
for(i=j-1;i;--i){
if(s[i-1]!=s[j-1])continue;
for(k=i;k<=j;++k){
if(s[i-1]!=s[k-1])continue;
dp[i][j]+=dp[i+1][k-1]*dp[k][j]%yyb;
}dp[i][j]%=yyb;
}
printf("%lld",dp[1][s.size()]);
return 0;
}
dfs实现：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
#define yyb 1000000000
using namespace std;
string s;
bool deal[301][301];
int dp[301][301];
il int dfs(int,int);
int main(){
cin>>s,printf("%d",dfs(1,s.size()));
return 0;
}
il int dfs(int l,int r){
if(l==r)return 1;
if(deal[l][r])return dp[l][r];
if(s[l-1]!=s[r-1])return 0;
for(int k(l+2);k<=r;++k)
if(s[k-1]==s[l-1])
(dp[l][r]+=(ll)dfs(l+1,k-1)*dfs(k,r)%yyb)%=yyb;
return deal[l][r]|=true,dp[l][r];
}