题意：给你一个字符串，问你有多少个树形结构。 思路：有dfs序那味道了，哈哈哈哈，然而是个区间dp，f[l][r]代表字符串从l到r中有多少种树形结构，状态转移不太好想，为了达到不重不漏的目的，我们通过枚举k来枚举第一个子树出现的大小，然后，只有在两端点相等的时候才能执行，因为最后要回到该点。其实k枚举到r-2或者r-3都是可以的，因为区间长度如果为2是不合法的。 ac代码：
#include<bits/stdc++.h> using namespace std; const int mod=1e9; typedef long long ll; ll dp[310][310]; int n; int main() { string s; cin>>s; n=s.size(); s= ' '+s; for(int i=1;i<=n;i++) dp[i][i]=1; for(int len=3;len<=n;len++) { for(int l=1;l+len-1<=n;l++) { int r=l+len-1; if(s[r]==s[l]) dp[l][r]=dp[l+1][r-1]; if(s[l]==s[r]) for(int k=l+1;k<=r-3;k++) dp[l][r]=(dp[l][r]+dp[l+1][k]*dp[k+1][r])%mod; } } cout<<dp[1][n]<<endl; }