516.最长回文子序列

发表于： 2023-07-02 分类于： leetcode

字数： 932 阅读：≈ 2分钟

🔄516.最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

思路

基本思想

本题与 647题有点类似，只不过647题求的是回文串的数量，并且是回文子串而不是回文子序列，也就是不能删除元素，本题可以删除元素，那么就会导致出现问题

本题中的dp[i][j]代表i~j范围内最长的回文子序列长度，当两个元素相等时，判断逻辑如下：

1
2
3
if(s[i]==s[j]){
    dp[i][j]=dp[i+1][j-1]+2;
}

当然有一种特殊情况，只有一个元素时，也满足s[i]==s[j]，可是此时不能+2，只能+1，所以这种情况单独拿出来统计，剩下的情况即使aa这种字符串，s[0]==s[1]，那么dp[0][1]=dp[1][0]+2

而dp[1][0]已经被初始化为0，所以不会有问题

当两个元素不相等时，类似于abac，此时a和c不匹配，但是可以去除一个元素，所以我们分别取出a和c，判断是否形成新的回文子串，是的话就更新dp数组，并且以去除元素形成的回文子序列作为当前的结果累加到后面，形成最终的结果，例如：

当前子串为abac，整体子串为abacaba，当前子串的回文子序列问aba，累加到后面，最终的结果为abaaba

理解如下的执行流程：

执行流程

初始化dp数组，全为0
按照更新逻辑更新dp数组
返回最终的结果

理解如下的执行流程：

忘记怎么做，就按照图，对着代码模拟一遍

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>>dp(s.size(),
                                vector<int>(s.size(),0));
        //s至少有一个元素，所以回文子序列的长度至少为1
        int res=1;
        //防止出现一个元素时，直接+2的情况
        for(int i=0;i<s.size();++i)
            dp[i][i]=1;
        for(int i=s.size()-1;i>=0;--i){
            //j从i+1开始，就是去除只有一个元素的情况
            //只有一个元素的情况单独处理了
            for(int j=i+1;j<s.size();++j){
                if(s[i]==s[j]){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    //当两个元素不相等时，判断去除一个元素会不会形成回文子序列
                    //abac的情况
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
                res=max(res,dp[i][j]);
            }
        }
        return res;
    }
};

总结

在 647题上做出改进，也是求当前子串是不是回文子串，并且当两个元素不相等时可以删除，如果删除之后可以形成回文子串，那么就可以累加到后面

并且由于判断逻辑，当前两个元素相等时，一次+2，所以只有一个元素的情况需要单独处理，j从i+1开始遍历，所以每次遍历至少有两个元素，+2符合逻辑