LeetCode_动态规划_中等_516.最长回文子序列

左手的ㄟ右手 2023-10-06 23:52 2阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

**示例 1：**  
输入：s = “bbbab”  
输出：4  
解释：一个可能的最长回文子序列为 “bbbb” 。

**示例 2：**  
输入：s = “cbbd”  
输出：2  
解释：一个可能的最长回文子序列为 “bb” 。

**提示：**  
1 <= s.length <= 1000  
s 仅由小写英文字母组成

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-palindromic-subsequence

## 2.思路 ##

（1）动态规划  
① 定义 dp 数组如下，dp\[i\]\[j\] 表示子串 s\[i…j\] 的最长回文子序列的长度

int[][] dp = new int[length][length];

② 状态转移方程。  
1）如果 s\[i\] == s\[j\]，那么**它们一定在最长回文子序列中**，dp\[i\]\[j\] = dp\[i + 1\]\[j - 1\] + 2;  
2）如果 s\[i\] != s\[j\]，此时则需要比较 s\[i + 1…j\] 和 s\[i…j - 1\] **谁的回文子序列更长**，dp\[i\]\[j\] = max(dp\[i + 1\]\[j\], dp\[i\]\[j - 1\]);

（2）最长公共子序列 & 动态规划  
本题也可以看作[LeetCode\_动态规划\_中等\_1143.最长公共子序列][LeetCode_1143.]这题的变形，为什么这么说呢？**如果将字符串 s 进行翻转得到 reversed\_s，那么 s 与 reversed\_s 的最长公共子序列即为 s 的最长的回文子序列**。

相关题目：  
[LeetCode\_动态规划\_中等\_5.最长回文子串][LeetCode_5.]  
[LeetCode\_回溯\_动态规划\_中等\_131.分割回文串][LeetCode_131.]  
[LeetCode\_双指针\_简单\_234.回文链表][LeetCode_234.]  
[LeetCode\_贪心算法\_简单\_409.最长回文串][LeetCode_409.]  
[LeetCode\_字符串\_中等\_647. 回文子串][LeetCode_647.]  
[LeetCode\_双指针\_简单\_1332.删除回文子序列][LeetCode_1332.]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public int longestPalindromeSubseq(String s) {
        
            int length = s.length();
            // dp[i][j] 表示子串 s[i..j] 的最长回文子序列的长度
            int[][] dp = new int[length][length];
            //初始化 dp
            for (int i = 0; i < length; i++) {
        
                dp[i][i] = 1;
            }
            for (int i = length - 1; i >= 0; i--) {
        
                for (int j = i + 1; j < length; 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], dp[i][j - 1]);
                    }
                }
            }
            // dp[0][length - 1] 即表示字符串 s 的最长的回文子序列的长度
            return dp[0][length - 1];
        }
    }

//思路2————最长公共子序列 & 动态规划
    class Solution {
        
        public int longestPalindromeSubseq(String s) {
        
            int length = s.length();
            String reversed_s = new StringBuilder(s).reverse().toString();
            // s 与 reversed_s 的最长公共子序列即为 s 的最长的回文子序列
            //dp[i][j] 表示 s[0...i-1]和 reversed_s[0...j-1] 的最长公共子序列(LCS)长度
            int[][] dp = new int[length + 1][length + 1];
            //初始化 dp
            //dp[0][...] = dp[...][0] = 0
            for (int i = 1; i <= length; i++) {
        
                for (int j = 1; j <= length; j++) {
        
                    if (s.charAt(i - 1) == reversed_s.charAt(j - 1)) {
        
                        // s[i-1] 和 reversed_s[j - 1] 在 LCS 中
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
        
                        // s[i-1] 和 reversed_s[j - 1] 至少有一个不在 LCS 中
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[length][length];
        }
    }

[LeetCode_1143.]: https://blog.csdn.net/weixin_43004044/article/details/123367960
[LeetCode_5.]: https://blog.csdn.net/weixin_43004044/article/details/118353990
[LeetCode_131.]: https://blog.csdn.net/weixin_43004044/article/details/125341429
[LeetCode_234.]: https://blog.csdn.net/weixin_43004044/article/details/122763107
[LeetCode_409.]: https://blog.csdn.net/weixin_43004044/article/details/126935075
[LeetCode_647.]: https://blog.csdn.net/weixin_43004044/article/details/124979183
[LeetCode_1332.]: https://blog.csdn.net/weixin_43004044/article/details/127058795