题目让我们求给定的一段字符串上回文串的长度（一个数也算是回文串），于是我就想怎样去找其中的规律，我举了些例子：
先是从相同的字符串开始举例“aaa”
对于aaa：dp[1][1]=1; dp[2][2]=1; dp[1][2]=dp[1][1]+dp[2][2]+1(因为1、2相同);......; dp[2][3]=dp[2][2]+dp[3][3]+1; dp[1][3]=dp[1][2]+dp[2][3]+1。显然，我们在相同的字符串上找到这样的规律：dp[i][j]=dp[i+1][j]+dp[i][j-1]+1。
其次，我们得处理不同字符串的情况，于是举例“abc”
对于abc：dp[1][1]=1; dp[2][2]=1; dp[1][2]=dp[1][1]+dp[2][2]; ......; dp[2][3]=dp[2][2]+dp[3][3]; dp[1][3]=dp[1][2]+dp[2][3]-1。诶，这里发现会多出来个“1”，什么情况！？显然，在不同的情况下会有哪个地方出现问题了，那么怎么处理？这里看到abc，会发现在处理到abc的时候，就会多处理了一次b，那么我们类比一下几组大的数据，遇到abcdasd这样，会发现，因为i、j处的字符不同，所以中间的这段字符串就会多加一次，所以需要删除中间的dp[i+1][j-1]，然而，相等的时候呢，abcdasa，此时由于头尾a的相等，故相当于中间部分的序列可以再外带一次外面的“a_a”，所以加上就没有问题。
状态转移方程：
-
s[i]==s[j]时候：dp[i][j]=dp[i+1][j]+dp[i][j-1]+1;
-
others：dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
-
细节：我WA了几发后意识到，此时需要运用到“-”，所以取模时先加上模值。
完整代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef long long ll;
const int maxN=1005;
const int mod=1e4+7;
char s[maxN];
int dp[maxN][maxN];
int main()
{
int T;
scanf("%d", &T);
for(int Cas=1; Cas<=T; Cas++)
{
getchar();
scanf("%s", s+1); memset(dp, 0, sizeof(dp));
int len=(int) strlen(s+1);
for(int i=1; i<=len; i++)
{
for(int j=i; j>=1; j--)
{
if(s[i] == s[j]) dp[j][i]=(dp[j+1][i] + dp[j][i-1] +1)%mod;
else dp[j][i]=(dp[j+1][i] + dp[j][i-1] - dp[j+1][i-1] + mod)%mod;
}
}
printf("Case %d: %d\n", Cas, dp[1][len]);
}
return 0;
}
