Light OJ 1025 - The Specials Menu（区间DP）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const int INF = 1e9+7;
const int MAXN = 255;
char str[MAXN];
LL dp[MAXN][MAXN];
LL DFS(int L,int R)
{
    if(L > R) return 0;
    if(dp[L][R]) return dp[L][R];
    if(L == R) return dp[L][R] = 1;

    dp[L][R] = DFS(L+1,R) + DFS(L,R-1) - DFS(L+1,R-1);
    if(str[L] == str[R])
        dp[L][R] += DFS(L+1, R-1) + 1;
    return dp[L][R];
}

int main()
{
    int T, cas = 1;
    scanf("%d", &T);
    while(T --)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%s", str);
        int len = strlen(str);
        printf("Case %d: %lld\n",cas ++, DFS(0,len-1));
    }

    return 0;
}