题意：给你一个字符串，问你整个字符串有多少个回文字串。（可以不连续）
状态方程 dp[i][j] = dp[i+1][j]+dp[i][j-1]+dp[i+1][j-1]+(a[i] == a[j]? 0:1;)
对于长度为1 2 3 的时候特判一下就可以了。
当然状态方程在些的时候会有改动，详细的还是看代码吧。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <vector> 7 #include <queue> 8 #define loop(s,i,n) for(i = s;i < n;i++) 9 #define cl(a,b) memset(a,b,sizeof(a)) 10 using namespace std; 11 const int mod = 10007; 12 char str[1005]; 13 int dp[1005][1005]; 14 int main() 15 { 16 int t; 17 18 scanf("%d",&t); 19 int cas; 20 cas = 0; 21 while(t--) 22 { 23 scanf("%s",str); 24 int i,j,len;len = strlen(str); 25 printf("Case %d: ",++cas); 26 27 memset(dp,0,sizeof(dp)); 28 for(i = 0;i < len;i++) 29 dp[i][i] = 1; 30 for(j = 2;j <= len;j++) 31 for(i = 0;i < len && i+j-1 < len;i++) 32 { 33 dp[i][i+j-1] = (dp[i+1][i+j-1]+dp[i][i+j-2]-dp[i+1][i+j-2])%mod;//减去中间重复计算的部分 34 35 if(str[i] == str[i+j-1]) 36 { 37 if(j > 2) 38 dp[i][i+j-1] =(dp[i][i+j-1]+ dp[i+1][i+j-2]+1)%mod;//大于2的时候计算一下中间的部分 39 else 40 { 41 dp[i][i+j-1] += 1; 42 dp[i][j+i-1] %= mod; 43 } 44 } 45 } 46 if(dp[0][len-1] < 0) 47 dp[0][len-1] += mod;//如果是负数要计算下+mod 48 printf("%d ",dp[0][len-1]); 49 } 50 return 0; 51 }