LA 3516 Exploring Pyramids (递推)

本文主要是介绍LA 3516 Exploring Pyramids (递推)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LA 3516 Exploring Pyramids

题目大意:

给一棵多叉树,从根节点开始,每次尽量往左走,走不通则回溯,将遇到的字母顺次记录下来,得到一个序列.现在给一个序列,求有多少棵树可以与之对应.

题目分析:

定义状态dp(i,j)表示序列[i,j]可形成的树的种类数。
设序列为S,因为在回溯的过程中也要记录,所以在选择某两个位置i和j时,需保证S[i]=S[j].
转移方程如下

$dp(i,j)=\sum dp(i+1,k-1)*dp(k,j)|S[i]=S[k]=S[j]$
边界为 $dp(i,i)=1,dp(i,j)=0|S[i]!=S[j]$

代码:

//递推
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;typedef long long ll;
const int MOD=1e9;
const int maxn=300+10;char S[maxn];
int d[maxn][maxn];int solve(int len)
{memset(d,0,sizeof(d));for(int i=0;i<len;i++) d[i][i]=1;for(int l=2;l<=len;l++)for(int s=0;s+l-1<len;s++) {int t=s+l-1;if(S[s]!=S[t]) continue;int& ans=d[s][t];for(int k=s+2;k<=t;k++) if(S[s]==S[k])ans=(ans+(ll)d[s+1][k-1]*d[k][t])%MOD;}return d[0][len-1];
}int main()
{while(~scanf("%s",S)) printf("%d\n",solve(strlen(S)));return 0;
}

//递归
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;typedef long long ll;
const int MOD=1e9;
const int maxn=300+10;char S[maxn];
int d[maxn][maxn];int dp(int i,int j)
{if(i==j) return 1;if(S[i]!=S[j]) return 0;int& ans=d[i][j];if(ans>=0) return ans;ans=0;for(int k=i+2;k<=j;k++) if(S[i]==S[k])ans=(ans+(ll)dp(i+1,k-1)*(ll)dp(k,j))%MOD;return ans;
}int main()
{while(~scanf("%s",S)) {memset(d,-1,sizeof(d));printf("%d\n",dp(0,strlen(S)-1));}return 0;
}