本文共 1092 字，大约阅读时间需要 3 分钟。

描述

给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中，回文子序列为"a", "a", "aa", "b", "aba"，共5个。内容相同位置不同的子序列算不同的子序列。

输入

第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。

输出

对于每组数据输出一行，格式为"Case #X: Y"，X代表数据编号（从1开始），Y为答案。答案对100007取模。

数据范围

1 ≤ T ≤ 30

小数据

字符串长度 ≤ 25

大数据

字符串长度 ≤ 1000

样例输入

5abaabcbaddabcba12111112351121cccccccfdadfa

样例输出

Case #1: 5Case #2: 277Case #3: 1333Case #4: 127Case #5: 17

Solution：

此题可以用动态规划的方法解决。申请二维数组dp[size][size],size为字符串长度。 dp[j][i] = dp[j+1][i]+dp[j][i-1]-dp[j+1][i-1]。如果str[j]=str[i]; 需要在加上新的回文序列 1+dp[j+1][i-1];  参见代码：

#include 
   
    #include 
    
     #include 
     
      using namespace std;int getPalindomNum(const string str){    size_t size = str.size();    int dp[size][size];    memset(dp,0,sizeof(dp));    for(int i=0; i
      
       =0; j--){            dp[j][i] = dp[j][i-1]+dp[j+1][i]-dp[j+1][i-1];            if(str[j]==str[i])                dp[j][i]+=dp[j+1][i-1]+1;            dp[j][i] = dp[j][i]%100007;        }            }    cout << dp[0][size-1]<
       
        > num;    while(cnt
        
         > str; int res = getPalindomNum(str); cout << "Case #" << cnt+1 << ": "<
         
          <
         
        
       
      
     
    
   

转载地址：http://iomab.baihongyu.com/