http://acm.hdu.edu.cn/showproblem.php?pid=4632
题意：
一个字符串，有多少个subsequence是回文串。
别人的题解：
用dp[i][j]表示这一段里有多少个回文串，那首先dp[i][j]=dp[i+1][j]+dp[i][j-1]，但是dp[i+1][j]和dp[i][j-1]可能有公共部分，所以要减去dp[i+1][j-1]。
如果str[i]==str[j]的话，还要加上dp[i+1][j-1]+1。
但是自己却是这样想的，把每个区间都要看是否为回文串，在dp[i][j]=dp[i+1][j]+1。我的想法是错误的，我忽略了每个区间都是一个递推的过程。
比如：aaa，a是一个回文串则外面2个aa只要判断是否相等就可以了就可以。如果区间两头是相等的，则要加上dp[j+1][i-1]+1，因为首尾是可以组成一个回文子串的，而且首尾可以与中间任何一个回文子串组成新的回文子。
其结果要取余，利用来了 dp[i][j]=(dp[i][j]+10007)%10007;
Palindrome subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65535 K (Java/Others)
Total Submission(s): 2246 Accepted Submission(s): 895
(http://en.wikipedia.org/wiki/Subsequence)
Given a string S, your task is to find out how many different subsequence of S is palindrome. Note that for any two subsequence X = <Sx1, Sx2, ..., Sxk> and Y = <Sy1, Sy2, ..., Syk> , if there exist an integer i (1<=i<=k) such that xi != yi, the subsequence X and Y should be consider different even if Sxi = Syi. Also two subsequences with different length should be considered different.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[][];
int main()
{
int t,k,i,j,g,len,r,p,q,e,m,b;
char str[];
cin>>q;
for(r=;r<=q;r++)
{
memset(dp,,sizeof(dp));
scanf("%s",str);
len=strlen(str);
for(i=;i<len;i++)
dp[i][i]=;//初始化，单个字符肯定是一个回文子串
for(k=;k<len;k++)
{
for(i=;i<len-k;i++)
{
j=i+k;
dp[i][j]=dp[i+][j]+dp[i][j-]-dp[i+][j-];////如果区间两头是相等的，则要加上dp[j+1][i-1]+1，
//因为首尾是可以组成一个回文子串的，而且首尾可以与中间任何一个回文子串组成新的回文子串
if(str[i]==str[j])
dp[i][j]+=dp[i+][j-]+;
dp[i][j]=(dp[i][j]+)%;//结果取余。
}
} printf("Case %d: %d\n",r,dp[][len-]);
}
return ;
}
/*
4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems
Case 1: 1
Case 2: 31
Case 3: 421
Case 4: 960
*/