516.最长回文子序列

水深无声 2024-03-01 08:13 68阅读 0赞

#### 516.最长回文子序列 ####

*  题干分析
 *  解题思路
 *   *  1. 确定dp数组（dp table）以及下标的含义
     *  2. 确定递推公式
     *  3. dp数组如何初始化
     *  4. 确定遍历顺序
     *  5. 举例推导dp数组
 *  代码实现

## 题干分析 ##

[力扣入口][Link 1]

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: “bbbab” 输出: 4 一个可能的最长回文子序列为 “bbbb”。

示例 2: 输入:“cbbd” 输出: 2 一个可能的最长回文子序列为 “bb”。

提示：

*  1 <= s.length <= 1000
 *  s 只包含小写英文字母

## 解题思路 ##

我们刚刚做过了 **动态规划：回文子串**，求的是回文子串，而本题要求的是回文子序列， 要搞清楚这两者之间的区别。

**回文子串是要连续的，回文子序列可不是连续的！** 回文子串，回文子序列都是动态规划经典题目。

回文子串，可以做这两题：

*  647.回文子串
 *  5.最长回文子串

思路其实是差不多的，但本题要比求回文子串简单一点，因为情况少了一点。

动规五部曲分析如下：

### 1. 确定dp数组（dp table）以及下标的含义 ###

dp\[i\]\[j\]：字符串s在\[i, j\]范围内最长的回文子序列的长度为dp\[i\]\[j\]。

### 2. 确定递推公式 ###

在判断回文子串的题目中，关键逻辑就是看s\[i\]与s\[j\]是否相同。

如果s\[i\]与s\[j\]相同，那么dp\[i\]\[j\] = dp\[i + 1\]\[j - 1\] + 2;

如图：  
![在这里插入图片描述][71d68454a19a4a109e1e0e48aebb5317.png]  
如果s\[i\]与s\[j\]不相同，说明s\[i\]和s\[j\]的同时加入并不能增加\[i,j\]区间回文子序列的长度，那么分别加入s\[i\]、s\[j\]看看哪一个可以组成最长的回文子序列。

加入s\[j\]的回文子序列长度为dp\[i + 1\]\[j\]。

加入s\[i\]的回文子序列长度为dp\[i\]\[j - 1\]。

那么dp\[i\]\[j\]一定是取最大的，即：dp\[i\]\[j\] = max(dp\[i + 1\]\[j\], dp\[i\]\[j - 1\]);  
![在这里插入图片描述][ae5d3e26313b4ee4be9f0620de2b4952.png]  
代码如下：

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]);
    }

### 3. dp数组如何初始化 ###

首先要考虑当i 和j 相同的情况，从递推公式：dp\[i\]\[j\] = dp\[i + 1\]\[j - 1\] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。

所以需要手动初始化一下，当i与j相同，那么dp\[i\]\[j\]一定是等于1的，即：一个字符的回文子序列长度就是1。

其他情况dp\[i\]\[j\]初始为0就行，这样递推公式：dp\[i\]\[j\] = max(dp\[i + 1\]\[j\], dp\[i\]\[j - 1\]); 中dp\[i\]\[j\]才不会被初始值覆盖。

### 4. 确定遍历顺序 ###

从递归公式中，可以看出，dp\[i\]\[j\] 依赖于 dp\[i + 1\]\[j - 1\] ，dp\[i + 1\]\[j\] 和 dp\[i\]\[j - 1\]，如图：  
![在这里插入图片描述][39d8057bf40c4df1823876adc492adb3.png]  
**所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。**

j的话，可以正常从左向右遍历。

### 5. 举例推导dp数组 ###

输入s:“cbbd” 为例，dp数组状态如图：  
![在这里插入图片描述][101bae62ddde43f2a9668d82529ac835.png]  
红色框即：dp\[0\]\[s.size() - 1\]; 为最终结果。

## 代码实现 ##

class Solution {
        
        // 516.最长回文子序列
        public int longestPalindromeSubseq(String s){
        
            int len = s.length();
            int[][] dp = new int[len + 1][len + 1];
            for(int i = len - 1; i >= 0; i--){
         // 从后往前遍历 保证情况不漏
                dp[i][i] = 1; // 初始化
                for(int j = i + 1; j < len; j++){
        
                    if (s.charAt(i) == s.charAt(j)) {
        
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
        
                        dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
                    }
                }
            }
            return dp[0][len - 1];
        }
    }

**参考资料**：[代码随想录-516.最长回文子序列][-516.]

[Link 1]: https://leetcode.cn/problems/longest-palindromic-subsequence/
[71d68454a19a4a109e1e0e48aebb5317.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/75e61804429b464496b29b15905faee1.png
[ae5d3e26313b4ee4be9f0620de2b4952.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/a6fcee3310b94ec88d7bb5a76f88340b.png
[39d8057bf40c4df1823876adc492adb3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/d2f1915fa182485790e1e407be065fce.png
[101bae62ddde43f2a9668d82529ac835.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/d32677e9bb6f40c0a05d9359930da822.png
[-516.]: https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE