题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4632
题意：给你一个序列，问你该序列中有多少个回文串子序列，可以不连续。
思路：dp[i][j]表示序列i到j中具有的回文串序列数。
当s[i]==s[j]， dp[i][j]=dp[i+1][j]+dp[i][j-1]+1
否则 dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]；
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <queue> 6 #include <algorithm> 7 using namespace std; 8 9 const int maxn=1024; 10 const int mod=10007; 11 int dp[maxn][maxn]; 12 char s[maxn]; 13 14 int main() 15 { 16 int T, tcase=0; 17 cin >> T; 18 while(T--) 19 { 20 scanf("%s",s+1); 21 int len=strlen(s+1); 22 memset(dp,0,sizeof(dp)); 23 for(int i=1; i<=len; i++) dp[i][i]=1; 24 for(int k=1; k<len; k++) 25 for(int i=1; i+k<=len; i++) 26 { 27 int j=i+k; 28 if(s[i]==s[j]) 29 { 30 if(k==1) dp[i][j]=3; 31 else dp[i][j]=(dp[i+1][j]+dp[i][j-1]+1)%mod;; 32 } 33 else dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;; 34 } 35 printf("Case %d: %d ",++tcase,dp[1][len]%mod); 36 } 37 return 0; 38 }