最长回文子序列

题目描述

给你一个字符串 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];
    }
};