UVa 10617

#include <bits/stdc++.h>

#define Max 70
#define i64 long long

i64 dp[Max][Max];
char str[Max];

int solve(int begin, int end) {
    if(begin == end)
        return 1;

    if(begin > end)
        return 0;

    if(dp[begin][end] != -1)
        return dp[begin][end];

    if(str[begin] == str[end])
        return dp[begin][end] = solve(begin, end - 1) + solve(begin + 1, end) + 1;
    else
        return dp[begin][end] = solve(begin, end - 1) + solve(begin + 1, end) - solve(begin + 1, end - 1);
}

int main(void) {
    int tcase;
    int length;
    scanf("%d", &tcase);
    while(tcase--) {
        int i, j, k;
        long long int temp;
        scanf("%s", str);
        length = strlen(str);
        memset(dp, 0, sizeof dp);
        for(i = 0; i < length; i ++)
            dp[i][i] = 1;

        for(int k = 1; k < length; k++)
            for(int i = 0; i < length - k; i++) {
                int j = i + k;
                if(str[i] == str[j])
                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + 1;
                else
                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
            }

     printf("%lld\n", dp[0][length - 1]);

     //top-down yields to TLE
     //memset(dp, -1, sizeof dp);
     //printf("%d\n", solve(0, length - 1));
    }
    return 0;
}