给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中，回文子序列为”a”, “a”, “aa”, “b”, “aba”，共5个。内容相同位置不同的子序列算不同的子序列。
第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。
对于每组数据输出一行，格式为”Case #X: Y”，X代表数据编号（从1开始），Y为答案。答案对100007取模。
1 ≤ T ≤ 30
小数据字符串长度 ≤ 25
大数据字符串长度 ≤ 1000
样例输入
5abaabcbaddabcba12111112351121cccccccfdadfa样例输出
Case #1: 5 Case #2: 277 Case #3: 1333 Case #4: 127 Case #5: 17
解题思路：
这道题初看起来非常复杂，涉及的情况非常多，一个长度为14的字符串（12111112351121）所包含的回文字符序列就高达1333种。所以对于一个特定的字符串，考虑其所有的情况显然是不大可能的。也正因为如此，可以很自然而然的联想到用动态规划来做。现在问题的关键就是如何构造其公式：
令dp(i,j)为字符串中第i位到第j位的子字符串所包含的回文字符序列，令str[i]表示字符串的第i位。下面需要分两种情况：
1、当str[i] = str[j]时,所有的回文序列由以下四部分组成
1）str[i]和str[j]与dp(i+1, j-1)中的所有的回文字符序列都能构成新的回文序列：dp(i+1, j-1)
2) 只考虑i不考虑j的回文序列:dp(i, j-1) - dp(i+1, j-1)
3) 只考虑j不考虑i的回文序列：dp(i+1,j) - dp(i+1, j-1)
4) i+1到j-1的回文序列：dp(i+1, j-1)
以上四部分相加即得到dp(i,j)= dp(i+1, j) + dp(i, j-1)
2、当str[i] != str[j]的时候，所有的回文序列由前面的2）3）4）三部分组成：
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) i+1到j-1的回文序列：dp(i+1, j-1)
以上三部分相加即得到dp(i,j)=dp(i+1, j) + dp(i, j-1) - dp(i+1, j-1)好了，有了这个公式，那么代码就好写了：
#include <iostream> #include <vector> #include <string> using namespace std; int get_palindrome_count_re(string str, int start, int end, int** dp) { if(dp[start][end] != -1) return dp[start][end]; if (str[start] == str[end]) { return get_palindrome_count_re(str, start, end - 1, dp) + get_palindrome_count_re(str, start + 1, end, dp) + 1; } else { return get_palindrome_count_re(str, start, end - 1, dp) + get_palindrome_count_re(str, start + 1, end, dp) - get_palindrome_count_re(str, start + 1, end - 1, dp); } } int get_palindrome_count(string str) { int** dp = new int*[str.length()]; for (int i = 0; i < str.length(); i++) { dp[i] = new int[str.length()]; } for(int i = 0; i < str.length(); i++) for (int j = 0; j< str.length(); j++) { if(i > j) dp[i][j] = 0; else if(i == j) dp[i][j] = 1; else dp[i][j] = -1; } int result = get_palindrome_count_re(str, 0, str.length() - 1, dp); for (int i = 0; i < str.length() ; i++) { int *tmp = dp[i]; delete []tmp; } delete []dp; return result; } int main() { int test_count; string str; vector<string> container; cin>>test_count; for (int i = 0; i < test_count; i++) { cin>>str; container.push_back(str); } for (int i = 0; i < test_count; i++) { int res = get_palindrome_count(container[i]); cout<<"Case #"<<i+1<<": "<<res<<endl; } return 0; }
相关资源：python入门教程(PDF版)
