LeetCode刷题实战516：最长回文子序列

栈长 • 2022年2月3日 13:52 • 编程技术 • 阅读 370

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最长回文子序列，我们先来看题面：

https://leetcode-cn.com/problems/longest-palindromic-subsequence/

Given a string s, find the longest palindromic subsequence’s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

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

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

示例

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

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

解题

https://www.cnblogs.com/luo-c/p/13948591.html

子序列是非连续的，子串是连续的，注意区分；

最大最小，最长最短，首先想到的就是动态规划，在子串 s[i…j] 中，最长回文子序列为 dp[i][j]，即，在二维数组 dp 中，i,j 的下标表示的是子串的起始终止位置，这个一定要理解；
对于 dp[i][j] , 如果 s[i] == s[j] ，则 d[i][j] = dp[i+1][j-1] + 2，如果 s[i] != s[j] ,则 dp[i][j] = max(dp[i+1][j], dp[i][j-1])；

由于长范围的子串 dp，需要依赖短的子串的结果，所以，先求 dp[n][n]，再求 dp[0][n]，只能斜着或者反着遍历：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = 1; //对角线上的单个元素为1
        for(int i = n-1; i >= 0; i--){
            for(int j = i+1; j < n; j++){ //先得到后面短的字符串，最后才得到全局的结果
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2; // i，j 是字符串中的位置，所以是 i+1, j-1
                }else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1]; //全部的字符串结果
    }
}