力扣：516.最长回文子序列_力扣516

一开始以为是最长回文子串，这题就跟上题基本一致了，代码如下。但是题目所说的是最长回文子序列，此时就相当于做了两题了。
最长回文子串代码：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),false));
        int result = 1; 
        for(int i = s.size()-1; i >= 0; --i){
            for(int j = i; j < s.size(); ++j){
                if(s[i] == s[j]) {
                    if(j - i <= 1){
                        dp[i][j] = true;
                    }
                    else if(dp[i+1][j-1]){
                        dp[i][j] = true;
                        if(j - i+1 > result) result = j-i+1;
                    }
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最长回文子序列：

力扣：516.最长回文子序列
题目：
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

解析：
然后还是很简单的，几分钟的事，还是首先通过for循环确定为二维dp数组，然后其含义为题目目的即 i ~ j 的最长回文子序列长度。然后脑海中举一个例子，然后考虑所有情况，用dp数组将其表示出来。

递归公式：

• 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
• 如果s[i]与s[j]不相同最长回文序列有两种情况，包含 i 的，包含 j 的，所以只需要进行比较即可。

初始化：
因为在递归公式中。当s【i】 == s【j】这种情况中其dp就默认了 i j 之间的长度大于1。所以应该考虑为 j - i 为1的情况。主观来看很明显应该是1。然后按照含义，递归公式，模拟遍历来初始化。此时按照含义即可初始化完成。其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。

递归顺序：
与上题分析一致。

最长回文子序列代码：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
        for(int i  = 0; i < s.size(); ++i) dp[i][i] = 1;
        for(int i = s.size()-1; i >= 0; --i){
           for(int j = i+1; j < s.size(); ++j){
               if(s[i] == s[j]){
                   dp[i][j] = 2+dp[i+1][j-1];                   
               }
               else {
                   dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
               }
           }
       }
    return dp[0][s.size()-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18