题意：

给出一个word，求有多少种方法你从这个word清除一些字符而达到一个回文串。

思路：

区间问题，还是区间DP；

我判断小的区间有多少，然后往外扩大一点。

dp[i,j]就代表从i到j的方案数。

状态转移：

其实对于在任意区间[i ,j]，都可以，

在子区间[i+1,j]中可以直接去掉s[j]时，顺便去掉s[i]，所以就有它的方案，

在子区间[i,j-1]中可以直接去掉s[i]时，顺便去掉s[j]，所以就有它的方案，

但是s[i],s[j]不相等的时候

dp[i+1,j]，dp[i,j-1]会重复一个情况（把s[i]和s[j]都删除了）

所以再减去一个dp[i+1,j-1]就好了；

相等的话，虽然可以直接把两端去掉，但是我们可以把多出来的这一部分首尾加上s[i]和s[j],

这样就又是不同的情况了，所以不需要再减去。

然后还有一种特殊的情况就是把区间[i+1, j-1]全部删完，只留一个s[i]和s[j]

膜泰巨blog【】

#include
     
      #include
      
       using namespace std;typedef long long LL;typedef unsigned long long ULL;const double eps=1e-5;const double pi=acos(-1.0);const int mod=1e8+7;const LL INF=0x3f3f3f3f;const int N=66;char s[N];LL solve(){    LL dp[N][N];    int len=strlen(s+1);    memset(dp,0,sizeof(dp));    for(int i=1;i<=len;i++)    {        for(int j=1;(j+i-1)<=len;j++)        {            int k=j+i-1;            dp[j][k]=dp[j+1][k]+dp[j][k-1];            if(s[j]==s[k])                dp[j][k]+=1;            else                dp[j][k]-=dp[j+1][k-1];        }    }    return dp[1][len];}int main(){    int cas=1;    int t;    scanf("%d",&t);    while(t--)    {        LL ans;        scanf("%s",s+1);        ans=solve();        printf("Case %d: %lld\n",cas++,ans);    }    return 0;}