516. 最长回文子序列(一般)

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

示例 1:

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

示例 2:

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

提示：

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

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

思路：

动态规划，dp[i ] [j]表示为最长回文子串的长度

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[s.length()][s.length()];
        //初始化对角线
        for(int i=0;i<len;i++){
            dp[i][i]=1;
        }
        for(int i=len-1;i>=0;i--){
            for(int j=i+1;j<len;j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;//如果相等，长度+2
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[] dp = new int[s.length()];
        //初始化1
        for(int i=0;i<len;i++){
            dp[i]=1;
        }
        for(int i=len-1;i>=0;i--){
            int pre = 0;
            for(int j=i+1;j<len;j++){
                int temp = dp[j];
                if(s.charAt(i)==s.charAt(j)){
                    dp[j]=pre+2;//如果相等，长度+2
                }else{
                    dp[j]=Math.max(dp[j],dp[j-1]);
                }
                pre = temp;
            }
        }
        return dp[len-1];
    }
}