AcWing 284. 金字塔（区间dp）

本文主要是介绍AcWing 284. 金字塔（区间dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。

经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。

首先，金字塔由若干房间组成，房间之间连有通道。

如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。

并且，每个房间的墙壁都涂有若干种颜色的一种。

探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。

这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。

机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。

最后，机器人会从入口退出金字塔。

显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次），然后，机器人会得到一个颜色序列。

但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。

现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。

因为结果可能会非常大，你只需要输出答案对109 取模之后的值。

输入格式
输入仅一行，包含一个字符串S，长度不超过300，表示机器人得到的颜色序列。

输出格式
输出一个整数表示答案。

输入样例：
ABABABA
输出样例：
5

思路：

类似dfs序，如果得到s[l] = s[r]，说明[l,r]之间的数都属于同一子树。
同一子树的结果满足加法原理，不同子树的结果满足乘法原理。记忆化搜索就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
const int mod = 1e9;
const int maxn = 305;
ll dp[maxn][maxn];
int n;
char s[maxn];ll dfs(int l,int r)
{if(l > r)return 0;if(l == r)return 1;if(s[l] != s[r])return 0;if(dp[l][r] != -1)return dp[l][r];dp[l][r] = 0;for(int k = l + 2;k <= r;k++){dp[l][r] = (dp[l][r] + dfs(l + 1,k - 1) * dfs(k,r)) % mod;//k为前一部分的分界点，如果把k作为后一部分的分界点，就会得到dfs(l+1,k) * dfs(k+1,r).但是k的起止点就成为了l+1,r-1。}return dp[l][r];
}int main()
{memset(dp,-1,sizeof(dp));scanf("%s",s + 1);n = (int)strlen(s + 1);ll ans = dfs(1,n);printf("%lld\n",ans);return 0;
}