【hihoCoder】回文字元序列

描述

給定字元串，求它的回文子序列個數。回文子序列反轉字元順序後仍然與原序列相同。例如字元串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      

【解析】

動态規劃。用dp[j][i]表示s[j...i]之間的回文子序列的個數，dp[j][i] = dp[j][i - 1] + dp[j + 1][i] - dp[j + 1][i - 1]，如果s[j] == s[i]，那麼還要加上s[j]s[i]兩個字元組成的子序列以及 s[j] + s[j+1][i-1]之間的子序列 + s[i] 組成的子序列。

【Java代碼】

import java.util.Scanner;
	
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        
        for (int t = 1; t <= T; t++) {
        	String s = in.next();
        	char[] ch = s.toCharArray();
        	int n = s.length();
        	
        	int[][] dp = new int[n][n];
        	
        	for (int i = 0; i < n; i++) {
        		dp[i][i] = 1;
        		for (int j = i - 1; j >= 0; j--) {
        			dp[j][i] = dp[j][i - 1] + dp[j + 1][i] - dp[j + 1][i - 1];
        			if (ch[j] == ch[i]) {
        				dp[j][i] += 1 + dp[j + 1][i - 1];
        			}
        		}
        		
        	}
        	
        	System.out.println("Case #" + t + ": " + dp[0][n - 1]);
        }
    }
}
           

免責聲明：題目來源于hihoCoder.com，如有侵權，請聯系部落客進行删帖。