DFS序列： 从点A出发到B，从点B出发到D，从点D出发返回B，从点B出发到E，从点E出发返回B······从点A出发到C，从点C出发到A。

从而得到DFS序列：ABDBEBFBACA

像不像一笔画。

知道流程后，我们可以发现一个规律，对于每一条边，我们都往返一次，共经历两次，对于n个顶点，我们有n - 1条边，而每一次经过边，都会搜索到一个点，所以DFS序列的长度为1（出发点） + 2 * （n - 1）= 2 * n - 1。

输入样例：

ABABABA

在样例中，DFS序列的长度为7，代入可得顶点的个数为4。

样例解释：

状态确立：

(这里R - 1是不合法的，因为最后一个点是n，R - 1不是一个DFS序列，最多是R - 2）

我们把一整条DFS序列拆出一个子链，那么这个子链是由红圈中的部分贡献的DFS序列。

但这些状态不是全部都成立的，合理的状态需要满足一个条件

K,L,R代表的字母必须相同

状态转移：

我们把树分为两部分，总的方案数为两方的方案数之积。

所以是f[L,R] = f[L,K] * f[K + 1,R]吗？

我们的方案数是左边的子树 * 右边的子树。

左边的子树是[L,R],右边的子树是[K + 1,R - 1]。

所以状态转移：

f[L,R] = f[L,K] * f[K + 1,R - 1]

我们最后再把所有不同种树的方案数相加，就得到最后的答案。

关于区间DP枚举方式的一点介绍：石子合并（算法竞赛进阶指南）_zyc_3的博客-CSDN博客

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9;
typedef long long ll;
ll f[305][305];
string st;
int n;
 
 
int main()
{
	cin >> st;
	n = st.size();
	
	if(n % 2 == 0){
		cout << 0;
	}//判断是否有解
	else{
		
		for(int len = 1;len <= n;len += 2)//len的变化是因为每次子树的点数变化，一个点对应来回两次，对DFS序列贡献为2
		{
			for(int l = 0;l + len - 1 < n;l ++)
			{
				int r = l + len - 1;
				if(len == 1)f[l][r] = 1;//初始化
				else if(st[l] == st[r]){
					for(int k = l;k < r;k += 2)//k += 2的理由同上 
					{
						if(st[k] == st[l])f[l][r] = (f[l][r] + f[l][k] * f[k + 1][r - 1]) % mod;//取不同的k值产生的f[l][r]要求总和
					}
				}
			}
		}
		cout << f[0][n - 1];
	}
	return 0;
}