HDU4632：Palindrome subsequence(區間DP)

Problem Description
In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence <A, B, D> is a subsequence of <A, B, C, D, E, F>.
(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.
 

Input
The first line contains only one integer T (T<=50), which is the number of test cases. Each test case contains a string S, the length of S is not greater than 1000 and only contains lowercase letters.
 

Output
For each test case, output the case number first, then output the number of different subsequence of the given string, the answer should be module 10007.
 

Sample Input
4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems

Sample Output
Case 1: 1
Case 2: 31
Case 3: 421
Case 4: 960

題意：找到一個字符串裡又多少個回文串子序列，要注意子序列的定義哦！

思路：這幾天做了幾道區間DP,這算是比較簡單的一道區間DP了，dp數組仍然是儲存區間內的回文串數，然後推導出狀態即可

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int mod = 10007;
char str[1005];
int dp[1005][1005];

int main()
{
    int t,i,j,k,len,cas = 1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",str);
        len = strlen(str);
        for(i = 0; i<len; i++)
            dp[i][i] = 1;//單個字符肯定是一個回文子串
        for(i = 1; i<len; i++)
        {
            for(j = i-1; j>=0; j--)
            {
                dp[j][i] = (dp[j+1][i]+dp[j][i-1]-dp[j+1][i-1]+mod)%mod;//之前沒有加mod，wa了，j~i的區間的回文數是j+1~i與j~i-1區間回文數的和，但是要注意這裡會有重復的
                if(str[i] == str[j])
                    dp[j][i] = (dp[j][i]+dp[j+1][i-1]+1+mod)%mod;//如果區間兩頭是相等的，則要加上dp[j+1][i-1]+1，因為首尾是可以組成一個回文子串的，而且首尾可以與中間任何一個回文子串組成新的回文子串
            }
        }
        printf("Case %d: %d\n",cas++,dp[0][len-1]);
    }

    return 0;
}