金字塔（区间DP或记忆化搜索）

题目：

给一个类似 $dfs$ 序的序列。（经过一个结点记录一次颜色）。问有多少棵有根树满足（结点子树之间有序）。答案 $mod1e9$ 输出。
$n≤300$

做法：

设 $dp[l][r]$ 为序列 $[l,r]$ 区间对应有根树的方案数，答案即为 $dp[1][n]$ 。
转移思路：我们枚举区间 $[l,r]$ 对应的有根树里，第一棵子树的区间，设为 $[l+1,k-1]$ ，则其他子树对应区间 $[k,r]$ 。
不难发现，合法的转移中 $s[l]=s[k]=s[r]$ ，此时有 $dp[l][r] += dp[l+1][k-1]*dp[k][r];$
最后加上只有一棵子树的情况： $dp[l][r]+=dp[l+1][r-1];$
区间 $dp$ 或记忆化搜索都能写，个人喜欢写 $dfs$ 。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 310;
const ll mod = 1e9;
char s[N];
ll dp[N][N];
ll dfs(int l, int r){
    if (~dp[l][r]) return dp[l][r];
    ll &ans = dp[l][r] = 0;
    if (l == r) return ans = 1;
    if (s[l] != s[r]) return ans = 0;
    if ((r-l+1)%2 == 0) return ans = 0;
    if (r-l+1 == 3) return ans = 1;
    ans = dfs(l+1, r-1);
    for (int i = l+2; i <= r-2; i += 2){
        if (s[i] == s[l]){
            ll L = dfs(l+1, i-1), R = dfs(i, r);
            ans = (ans + L*R%mod)%mod;
        }
    }
    return ans;
}
int main(void){
    IOS;
    cin >> (s+1);
    int n = strlen(s+1);
    memset(dp, -1, sizeof dp);
    cout << dfs(1, n) << endl;
    return 0;
}