给定dfs序列 求有多少中可能的树形结构

保证不重复: 我们只枚举第一个子树的情况

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
const int N=305;
const int mod=1e9;
using namespace std;
int read()
{
	int x=0,f=0,c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f?-x:x;
}
char s[N];
int f[N][N]; 
int n;

int main()
{
	scanf("%s",s+1); n=strlen(s+1);
	for(int i=1;i<=n;i++) f[i][i]=1;
	for(int len=2;len<=n;len++)
		for(int l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			if(s[l]==s[r])
			{
				f[l][r]=((ll)f[l][r]+f[l+1][r-1])%mod;
					for(int k=l+2;k<=r-2;k++)
						if(s[l]==s[k])
							f[l][r]=((ll)f[l+1][k-1]*f[k][r]+f[l][r])%mod;
			}
				
		}
	printf("%d",f[1][n]);

	return 0;
}