hdu4632 Palindrome subsequence--区间dp

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=4632​​

题意：求一个字符串所有子序列是回文的个数，注意子序列是这样的情况：原串abcde，子串abd。注意与子串含义不同。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

int t;
int dp[1005][1005];//dp[i][j]表示i到j区间内的种数 
char s[1005];

int main()
{
  scanf("%d", &t);
  for (int cas = 1; cas <= t; cas++)
  {
    scanf("%s", s);
    int len = strlen(s);
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < len; i++)
      dp[i][i] = 1;

    for (int j = 0; j < len; j++)
    {
      for (int i = j - 1; i >= 0; i--)
      {
        dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + 10007) % 10007; //j~i的区间的回文数是j+1~i与j~i-1区间
                                                                                                   //回文数的和，但是要注意这里会有重复的  
        if (s[i] == s[j])
          dp[i][j] = (dp[i][j] + dp[i + 1][j - 1] + 1) % 10007;如果区间两头是相等的，则要加上dp[j+1][i-1]+1，
//因为首尾是可以组成一个回文子串的，而且首尾可以与中间任何一个回文子串组成新的回文子串
      }
    }

    printf("Case %d: %d\n", cas, dp[0][len - 1]);
  }


  return 0;
}