微軟程式設計之美——回文字元序列

給定字元串，求它的回文子序列個數。回文子序列反轉字元順序後仍然與原序列相同。例如字元串aba中，回文子序列為”a”, “a”, “aa”, “b”, “aba”，共5個。内容相同位置不同的子序列算不同的子序列。

時間限制:2000ms

單點時限:1000ms

記憶體限制:256mb

第一行一個整數t，表示資料組數。之後是t組資料，每組資料為一行字元串。

對于每組資料輸出一行，格式為”case #x: y”，x代表資料編号（從1開始），y為答案。答案對100007取模。

1 ≤ t ≤ 30

小資料

字元串長度 ≤ 25

大資料

字元串長度 ≤ 1000

樣例輸入

5

aba

abcbaddabcba

12111112351121

ccccccc

fdadfa

樣例輸出

case

#1: 5

#2: 277

#3: 1333

#4: 127

#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)

好了，有了這個公式，那麼代碼就好寫了：