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 =  + ;
 const int MOD = ; char s[maxn];
 int d[maxn][maxn]; int dp(int i, int j)
 {
     if(i == j) return ;
     if(s[i] != s[j]) return ;
     int& ans = d[i][j];
     if(ans >= ) return ans;     ans = ;
     for(int k = i + ; k <= j; k++) if(s[i] == s[k])
         ans = (ans + (LL)dp(i+, k-) * (LL)dp(k, j)) % MOD;
     return ans;
 } int main()
 {
     while(scanf("%s", s) == )
     {
         memset(d, -, sizeof(d));
         printf("%d\n", dp(, strlen(s) - ));
     }     return ;
 }

代码君