原文链接: 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.

 

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

 

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

中文题目

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

通过代码

高赞题解

解题思路：

• 状态
  f[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。

• 转移方程
  如果 s 的第 i 个字符和第 j 个字符相同的话

  f[i][j] = f[i + 1][j - 1] + 2

  如果 s 的第 i 个字符和第 j 个字符不同的话

  f[i][j] = max(f[i + 1][j], f[i][j - 1])

  然后注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了。

• 初始化
  f[i][i] = 1 单个字符的最长回文序列是 1

• 结果
  f[0][n - 1]

代码如下：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
}

统计信息

通过次数	提交次数	AC比率
92593	140974	65.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
最长回文子串	中等
回文子串	中等
统计不同回文子序列	困难