時間限制:2000ms
單點時限:1000ms
內存限制:256MB
描述
給定字符串，求它的回文子序列個數。回文子序列反轉字符順序後仍然與原序列相同。例如字符串aba中，回文子序列為”a”, “a”, “aa”, “b”, “aba”，共5個。內容相同位置不同的子序列算不同的子序列。
輸入
第一行一個整數T，表示數據組數。之後是T組數據，每組數據為一行字符串。
輸出
對於每組數據輸出一行，格式為”Case #X: Y”，X代表數據編號（從1開始），Y為答案。答案對100007取模。
數據范圍
1 ≤ T ≤ 30
小數據
字符串長度 ≤ 25
大數據
字符串長度 ≤ 1000
樣例輸入
5
aba
abcbaddabcba
12111112351121
ccccccc
fdadfa
樣例輸出
Case #1: 5
Case #2: 277
Case #3: 1333
Case #4: 127
Case #5: 17
分析：
1. 區間型DP， 先來說一下狀態方程： 如求i到j這個區間共有多少回文子序列 ，兩種情況①當s[i] == s[j]時，例如“a….a”，d[i][j] = d[i][j-1] + d[i+1][j] + 1(由d[i][j] = 2*d[i+1][j-1] + d[i][j-1] + d[i+1][j] + 1 - 2*d[i+1][j-1] 化簡來的。 解釋：已知 i+1 到 j-1 有d[i+1][j-1]個回文子序列， 又有s[i] == s[j], 那麼可與中間（串i+1到j-1）已知的回文子序列再構成d[i+1][j-1]個回文子序列，再加上原來中間串所包含的回文子序列共2*d[i+1][j-1]個， 兩個a組合”aa”也是回文, 所以再加1， 再分別計算左、右兩邊的a和中間串所構成的回文子序列， 但是這個時候還沒完，注意：在分別計算左右兩邊a和中間串時，又算了兩遍中間串包含的回文子序列， 所以在減去2*d[i+1][j-1]個)；②當s[i] != s[j]時，d[i][j] = d[i][j-1]+d[i+1][j] - d[i+1][j-1]。這個自己應該也能分析出來，和上面類似。
2. 求區間i到j時， 會用到d[i+1][j-1], d[i][j-1], d[i+1][j]。 這也正是為什麼區間型DP一般都是從相距較小的區間開始， 然後不擴大區間。當下所求區間(i, j)所用的子區間，之前都已求完，so還是那句話，直接用就好啦。
那個地方意見不一致歡迎指出，互相學習！！
