算法1
O(N^3)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
// Tag: 区间DP 求方案数
/*
出现的次数为 该结点 的 子节点数 + 1。
和树的DFS序类似。一棵树的深度优先遍历 和 得到的区间有联系,
故可以用子区间来表示子树进而组成整棵树(整个区间)
状态表示:
f[l,r] 代表区间 [l,r] 所代表的树能组成的 树 的方案总数。
属性:方案数,所以要求状态的划分不重不漏。
为了保证计数不重不漏,可以只考虑字串 S[l~r] 的第一棵子树是由哪一段构成的。
枚举划分点 k ,令字串 S[l+1~k-1] 构成 [l,r] 的第一棵子树,如果 k 不相同,
那么字串 S[l+1~k-1] 代表的子树大小也不相同,故不可能产生重复计算。
状态计算:
F[l,r] = { 0, S[l] != S[r]
{ F[l+1,r-1] + F[l+1,k-1] * F[k,r] (k<=r-2 && k>=l+2) S[l] == S[r]
初始化: f[l][l] = 1, l∈[1,N], 其余均为0。
*/
/*
对于记录方案数这种DP问题。
通常一个状态的各个决策之间满足“加法原理”,而每个决策的划分的
几个子状态之间满足“乘法原理”。而一个状态的所有决策之间必须 互斥,
才能保证不会出现重复问题。
*/
typedef long long LL;
const int mod = 1e9, N = 310;
int f[N][N];
char str[N];
int main()
{
cin>>str+1;
int n=strlen(str+1);
//每条边连接两个结点,而最初的起点不算在内,所以区间的总长度一定为奇数
if(n%2==0) cout<<0<<endl;
else
{
for(int len = 1; len<=n; len+=2)
{
for(int l = 1;l+len-1<=n;l++)
{
int r=l+len-1;
if(len==1) f[l][r]=1;
else if(str[l]==str[r])
{
for(int k=l;k<r;k+=2)
if(str[k]==str[r])
f[l][r] = (f[l][r] + (LL)f[l][k]*f[k+1][r-1]%mod)%mod;
}
}
}
cout<<f[1][n]<<endl;
}
return 0;
}
记忆化
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9, N = 310;
int f[N][N];
char str[N];
int solve(int l,int r)
{
if(l>r) return 0;
if(l==r) return 1;
if(f[l][r]!=-1) return f[l][r]; //记忆化
f[l][r] = 0;
if(str[l]==str[r])
for(int k=l+2;k<=r;k++)
{
f[l][r] = (f[l][r] + (LL)solve(l+1,k-1)*solve(k,r)%mod)%mod;
}
return f[l][r];
}
int main()
{
cin>>str+1;
int n=strlen(str+1);
//每条边连接两个结点,而最初的起点不算在内,所以区间的总长度一定为奇数
if(n%2==0) cout<<0<<endl;
else
{
memset(f,-1,sizeof f);
cout<<solve(1,n)<<endl;
}
return 0;
}