题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4632

题目大意

给你一个长度为N（N≤1000）的字符串，你输出它所有的回文子序列的数量（对10007取模）。
只要从字符串 s 中顺序地取出一些字符（不要求连续，可以是 s 本身，不能是空串），不改变他们的顺序的情况下，这个子序列是一个回文串，那么他就是一个 s 的回文子序列。
【输入格式】
首先是一个数T（T≤50），表示测试用例的数量。
接下来T行，每行包含一个字符串。
【输出格式】
对于每一个字符串，你需要输出它的回文子序列数量（由于数据量可能会比较大，所以结果需要对10007取模）。
【样例输入】
4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems
【样例输出】
Case 1: 1
Case 2: 31
Case 3: 421
Case 4: 960

解题思路

区间dp。（要不是专门搜的区间dp的题目，真不一定知道用区间dp）
dp表示某区间内回文子序列的数量。
当区间端点字符不一样时，由容斥原理得
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]
当区间端点字符一样时，除了上述部分还要加上两端点内的回文子序列数量+1，因为两端点内存在dp[i+1][j-1]种回文子序列与俩端点匹配构成新的回文子序列，同时还有不选两端点内任何一回文子序列，所以，
dp[i][j]=dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1] + dp[i+1][j-1] + 1 = dp[i][j-1] + dp[i+1][j] + 1

AC代码

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
const int N=1e3+10;
int dp[N][N];
int T;
string str;
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        memset(dp,0,sizeof dp);
        cin>>str;
        int n=str.size();
        str='.'+str;
        for(int i=1;i<=n;i++) dp[i][i]=1;
        for(int len=2;len<=n;len++)
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                if(str[i]==str[j]) dp[i][j]=dp[i+1][j-1]+1;
                dp[i][j]=(dp[i][j]+dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;
            }
        printf("Case %d: %d\n",t,dp[1][n]);
    }
}

我的错因

菜是原罪。
当时，我考虑两端点相同与不同两情况的时候，潜意识里把dp理解错了，理解成了个很难形容的含义（不知道你有的时候有没有这种神（S）犇（B）情况）。最后还笃定自己的转移方程的思路没问题，结果直接GG。
不过大思路确实没错（给自己台阶下），
相等时，与两端点内的数量有关；
不相等时，还要单独加上端点内部与端点能构成回文子序列的数量。
真是难受，直接把dp数组“理解”错了（更气的是……哎不说了，表达不出来，好难受~~）