一道区间dp题，容易设计状态表示f[l][r]表示s[l~r]可能对应多少中金字塔方案数。
我们考虑在[l,r]中枚举一个k使得[l+1,k-1]作为l的一棵子树。那么s[l]应该等于s[k]，状态转移方程为f[l][r]=∑f[l+1][k-1]*f[k][r];
注意数据范围可能超过int，所以最好用long long存储，而且本题可以用记忆化搜索解决。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define mod 1000000000 5 using namespace std; 6 char s[310]; 7 int f[310][310]; 8 int dfs(int l,int r) { 9 if(l>r) return f[l][r]=0; 10 if(l==r) return f[l][r]=1; 11 if(f[l][r]!=-1) return f[l][r]; 12 f[l][r]=0; 13 for(int k=l+2;k<=r;k++) 14 if(s[l]==s[k]) 15 f[l][r]=(f[l][r]+1ll*dfs(l+1,k-1)*dfs(k,r)%mod)%mod; 16 return f[l][r]%mod; 17 } 18 int main() { 19 memset(f,-1,sizeof(f)); 20 scanf("%s",s+1); 21 int n=strlen(s+1); 22 dfs(1,n); 23 printf("%d ",f[1][n]%mod); 24 return 0; 25 }