题目链接：http://hihocoder.com/problemset/problem/1149
题意：给定字符串，求它的回文子序列个数。这里的子序列是指一个序列中去掉一些元素，剩余的元素按顺序组成的序列。
解析：又是一种dp，想明白dp的思路就好，由于做dp不多所以记录下：
用dp[i][j]表示区间[i,j]中回文子序列的个数，那么对于dp[i][i]=1是计算的基础，下面分析状态转移：在求f[i, j]时，注意到
1.包含第i个字符且不包含第j个字符的回文子序列个数为dp[i, j-1] - dp[i+1, j-1]，
2.包含第j个字符且不包含第i个字符的回文子序列个数为dp[i+1, j] - dp[i+1, j-1]，
3.均不包含则是dp[i+1, j-1]，
4.均包含则是dp[i+1, j-1] + 1。
基本思路是，求区间[i,j]中回文子序列的个数dp[i][j]可以用[i+1,j-1]中回文子序列个数，加上i元素与区间[i+1,j-1]形成的新的回文子序列的个数，再加上j元素与区间[i+1,j-1]形成的新的回文子序列的个数。
即dp[i, j]=(dp[i, j-1] - dp[i+1, j-1])+(dp[i+1, j] - dp[i+1, j-1])+dp[i+1, j-1]=dp[i, j-1] + dp[i+1, j] - dp[i+1, j-1]
然后在此基础上发现当str[i]==str[j]时，区间[i+1,j-1]中的所有回文子序列两端分别加上str[i]和str[j]形成的序列仍然是回文的，而且（str[i],str[j]）本身就是回文的。此时在上面基础上dp[i][j]+=（dp[i+1, j-1]）+1
因此列出递推式：
如果str[i] != str[j]，dp[i, j] = dp[i, j-1] + dp[i+1, j] - dp[i+1, j-1]；
如果str[i]==str[j]，dp[i, j] = dp[i, j-1] + dp[i+1, j] + 1；
参考：http://wangshenghu.github.io/blog/2016/05/17/hihocoder-palindrome-sub-sequence/
代码：
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
#define M 1010
#define mod 100007
char str[M];
int dp[M][M];
int main()
{int T,i,j,len,n,cas=0;scanf("%d",&T);while(T--){scanf("%s",str+1);memset(dp,0,sizeof(dp));n=strlen(str+1);for(len=0;len<n;len++){for(i=1;i+len<=n;i++){j=i+len;if(str[i]==str[j])dp[i][j]=(dp[i+1][j]+dp[i][j-1]+1)%mod;elsedp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;}}printf("Case #%d: %d\n",++cas,dp[1][n]);}return 0;
}