#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
const int maxn =
310;
const ll mod =
1e9;
char s[maxn];
ll dp[maxn][maxn];
ll solve(int i,
int j) {
if(i == j)
return 1;
if(s[i] != s[j])
return 0;
ll& ans =
dp[i][j];
if(ans >=
0)
return ans;
ans =
0;
for(
int k = i +
2; k <= j; k++)
if(s[i] ==
s[k]) {
ans = (ans + solve(i+
1, k-
1) * solve(k, j)) %
mod;
}
return ans;
}
int main() {
while(~scanf(
"%s", s)) {
memset(dp, -
1,
sizeof(dp));
cout << solve(
0, strlen(s) -
1) <<
endl;
}
}
转载于:https://www.cnblogs.com/lonewanderer/p/5701031.html
相关资源：JAVA上百实例源码以及开源项目
