【区间dp】【记忆化搜索】UVALive

f(i,j)=sum(f(i+1,k-1)*f(k,j) | i+2<=k<=j，Si=Sk=Sj）。

f(i+1,k-1)是划分出第一颗子树，f(k,j)是划分出剩下的子树。

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define MOD 1000000000ll
char s[310];
ll f[310][310];
int n;
ll dp(int l,int r){
	if(f[l][r]!=-1){
		return f[l][r];
	}
	f[l][r]=0;
	for(int k=l+2;k<=r;++k){
		if(s[l]==s[k]){
			f[l][r]=(f[l][r]+dp(l+1,k-1)*dp(k,r)%MOD)%MOD;
		}
	}
	return f[l][r];
}
int main(){
//	freopen("uvaLive3516.in","r",stdin);
	while(scanf("%s",s+1)!=EOF){
		memset(f,-1,sizeof(f));
		n=strlen(s+1);
		for(int i=1;i<=n;++i){
			f[i][i]=1;
		}
		for(int i=1;i<=n;++i){
			for(int j=i+1;j<=n;++j){
				if(s[i]!=s[j]){
					f[i][j]=0;
				}
			}
		}
		printf("%d
",(int)dp(1,n));
	}
	return 0;
}