给一个字符串，问有几种删字符的方式使删后的非空字符串是个回文串。
当然区间DP：dp[i][j]表示子串stri...strj的方案数
感觉不好转移，可能重复算了。我手算了"AAA"这个数据，然后就搞出转移的方式：
d[i][j] = ∑ d[i'][j']+1 （i<=i'<=j'<=j 且 str[i']==str[j']）
这个区间DP和经典例题相邻石子合并一样，枚举长度然后枚举起点，这样保证计算过程的拓扑有序。时间复杂度O(strlen4)。
#include<cstdio>
#include<cstring>
using namespace std;
char str[];
long long d[][];
int main(){
int t;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%s",str);
int n=strlen(str);
memset(d,,sizeof(d));
for(int len=; len<=n; ++len){
for(int k=; k+len<=n; ++k){
d[k][k+len-]=len;
for(int i=; i<len; ++i){
for(int j=i+; j<len; ++j){
if(str[k+i]!=str[k+j]) continue;
d[k][k+len-]+=d[k+i+][k+j-]+;
}
}
}
}
printf("Case %d: %lld\n",cse,d[][n-]);
}
return ;
}