大廠面試真題詳解：最長的迴文序列

給一字符串 s, 找出在 s 中的最長迴文子序列的長度. 你可以假設 s 的最大長度為 1000.

在線評測地址：領釦題庫官網

樣例1

輸入： "bbbab"
輸出： 4
解釋：
一個可能的最長迴文序列為 "bbbb"

樣例2

輸入： "bbbbb"
輸出： 5

算法：DP

設dpi表示在s[i...j]中最長迴文序列的長度。
對於初始化區間長度

• 長度為0時，dpi = 1

• 對於 dpi，假設s[i] != s[j]

  • 那麼在sub(i,j)的最大回文串中,s[i]與s[j]不會同時出現，那麼sub(i,j)的最大回文串要麼出現在sub(i+1,j),要麼出現在sub(i,j-1)，因此我們的狀態轉移方程就得到了dpi = max(dpi+1, dpi)

• 假設s[i]==s[j]

  • 那麼直接認為這倆個匹配，會同時出現在結果中，然後加上sub(i+1,j-1)的最大回文串，即dpi = dpi+1 + 2
• 最後的結果就在dp0

複雜度分析

• 時間複雜度O(len(s)*len(s))

  • 嵌套循環，順著i減小的方向，以j增大的方向遍歷

• 空間複雜度O(len(s)*len(s))

  • 二維dp的大小

public class Solution {
    /**
     * @param s: the maximum length of s is 1000
     * @return: the longest palindromic subsequence's length
     */
    public int longestPalindromeSubseq(String s) {
        int size = s.length();
        char[] ss = s.toCharArray();
        if (size <= 1){
            return size;
        }
        int[][] dp = new int[size][size];
        //初始化        
        for (int i = 0; i < size; ++i) {
            dp[i][i] = 1;
        }
        for (int i = size - 1; i >= 0; --i) {
            for (int j = i + 1; j < size; ++j) {
                if (ss[i] == ss[j]) {//s[i]==s[j]時的轉移方程
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } 
                else {//s[i]！=s[j]時的轉移方程
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        //最後結果在dp[0][size - 1]中
        return dp[0][size - 1];
    }
}

更多題解參考：九章官網solution