LA 3516 (计数 DP) Exploring Pyramids

设d(i, j)为连续子序列[i, j]构成数的个数，因为遍历从根节点出发最终要回溯到根节点，所以边界情况是：d(i, i) = 1; 如果s[i] != s[j], d(i, j) = 0

假设第一个分支在S_k回到根节点，方案数为d(i+1, k-1)

其他分支访问从S_k到S_j，方案数为d(k, j)

根据乘法原理，d(i, j) = sum{d(i+1, k-1), d(k, j), i+2≤k≤j 且 S_i = S_k = S_j}

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int maxn = 300 + 10;
const int MOD = 1000000000;

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) == 1)
    {
        memset(d, -1, sizeof(d));
        printf("%d
", dp(0, strlen(s) - 1));
    }

    return 0;
}