LeetCode——516. 最长回文子序列(Longest Palindromic Subsequence)[中等]——分析及代码（Java）

一、题目

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

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

示例 1：

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

示例 2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析及代码

1. 动态规划

（1）思路

设计一个动态规划数组 dp，其中 dp[i][j] 表示区间 [i, j] 内最长回文子序列的长度，则

• 若 s.charAt(i) == s.charAt(j), dp[i][j] = dp[i + 1][j - 1] + 2
• 若 s.charAt(i) != s.charAt(j)，dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])

完成全部遍历后，得到的 dp[0][n - 1] 就是整个字符串中最长回文子序列的长度。

（2）代码

class Solution {
    public int longestPalindromeSubseq(String s) {
        //初始化
        char[] str = s.toCharArray();//转为char[]，简化代码
        int n = str.length;//字符串长度
        int[][] dp = new int[n][n];//dp[i][j]表示区间[i,j]内最长回文子序列的长度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                dp[i][j] = 0;//初始化为0
            dp[i][i] = 1;//单个字符是长度为1的回文子序列
        }

        //动态规划
        for (int i = n - 1; i >= 0; i--) {//遍历左边界
            for (int j = i + 1; j < n; j++) {//遍历右边界，[i,j]区间范围应从小到大，因此右边界遍历方向和左边界相反
                if (str[j] == str[i])//两端字符相同
                    dp[i][j] = dp[i + 1][j - 1] + 2;//最长回文子序列长度+2
                else//两端字符不同
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);//长度为范围-1区间对应的较大值
            }
        }
        return dp[0][n - 1];//整个字符串对应的最长回文子序列长度
    }
}

（3）结果

执行用时 ：30 ms，在所有 Java 提交中击败了 88.63% 的用户；
内存消耗 ：48.6 MB，在所有 Java 提交中击败了 17.58% 的用户。

三、其他

暂无。