最長回文子序列

題目描述

給你一個字元串 s ，找出其中最長的回文子序列，并傳回該序列的長度。

子序列定義為：不改變剩餘字元順序的情況下，删除某些字元或者不删除任何字元形成的一個序列。

• 1 <= s.length <= 1000
• s 僅由小寫英文字母組成

題解

我這道題的解題思路是區間dp，使用一個二維數組記錄這個一個區間内最長的回文子序列。當區間長度為1的時候，很顯然最長回文子串的長度是1。當區間長度為2的時候要進行判斷，如果兩個字元串相等的，則最長回文子序列的長度是2，否則是1。當區間長度大于2的時候，我們會從區間長度為3開始周遊，我們會一步步從小區間的最優結果慢慢的到稍大區間的結果，以緻最後得到整個區間的結果。

狀态轉移方程如下：

d p [ i ] [ j ] = { 1 i = = j 或 者 i + 1 = = j , s [ i ] ! = s [ j ] 2 i + 1 = = j , s [ i ] = = s [ j ] m a x ( d p [ i + 1 ] [ j ] , d p [ i ] [ j − 1 ] ) j − i > 1 , s [ i ] = = s [ j ] d p [ i + 1 ] [ j − 1 ] + 2 j − i > 1 , s [ i ] ! = s [ j ] \begin{aligned} dp[i][j]=\left\{ \begin{array}{clc} 1 & & i == j 或者 i+1==j,s[i]!=s[j]\\ 2 & & i+1==j,s[i]==s[j]\\ max(dp[i+1][j], dp[i][j-1]) & & j-i>1,s[i] == s[j]\\ dp[i+1][j-1]+2 & &j-i>1,s[i] != s[j] \end{array} \right. \end{aligned} dp[i][j]=⎩⎪⎪⎨⎪⎪⎧​12max(dp[i+1][j],dp[i][j−1])dp[i+1][j−1]+2​​i==j或者i+1==j,s[i]!=s[j]i+1==j,s[i]==s[j]j−i>1,s[i]==s[j]j−i>1,s[i]!=s[j]​​

其中，dp[i][j]，表示在區間[i, j]内最長的回文子序列的長度。

C++代碼

class Solution {
public:
    int dp[1003][1003];
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        if(n<2) return n;
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<=n;i++) dp[i][i] = 1;
        for(int i=1;i<n;i++) {
            if(s[i-1] == s[i]) dp[i-1][i] = 2;
            else dp[i-1][i] = 1;
        }

        for(int len = 3;len<=n;len++){
            for(int i=0;i+len<=n;i++){
                int j = i+len-1;
                if(s[i] == s[j]){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
};