leetcode 516. 最长回文子序列(JAVA)题解

布满荆棘的人生 2023-10-14 19:43 26阅读 0赞

[题目链接![icon-default.png_t_N6B9][]https://leetcode.cn/problems/longest-palindromic-subsequence/description/?utm\_source=LCUS&utm\_medium=ip\_redirect&utm\_campaign=transfer2china][icon-default.png_t_N6B9_https_leetcode.cn_problems_longest-palindromic-subsequence_description_utm_source_LCUS_utm_medium_ip_redirect_utm_campaign_transfer2china]

**目录**

题目描述：

暴力递归：

动态规划：

--------------------

# **题目描述：** #

**给你一个字符串 `s` ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。**

> **示例 1：**
> 
>     输入：s = "bbbab"
>     输出：4
>     解释：一个可能的最长回文子序列为 "bbbb" 。
> 
> **示例 2：**
> 
>     输入：s = "cbbd"
>     输出：2
>     解释：一个可能的最长回文子序列为 "bb" 。
> 
> **提示：**
> 
>  *  `1 <= s.length <= 1000`
>  *  `s` 仅由小写英文字母组成

这道题的知识点是**动态规划**，可是如果直接从动态规划讲可能有点不容易理解。

所以本篇文章就是从暴力递归到动态规划。

从题目中我们可以得出：本题找的是可以不连续的回文子串然后返回其最大**序列的长度。**

> **也就是说：**
> 
> **a2b42a**
> 
> 的最长回文子序列为：**a2b2a或a242a** 这两个**都可以**因为它们**返回的都是5**

# 暴力递归： #

我们先写一个可以返回最长的回文子序列长度的函数：

我们写的 maxString() 方法可以返回 str 字符串\[l, r\]区间的最长回文子序列的长度 。

**通过分析可以得出以下结论：**

**两种特殊情况：**

*  首先我们可以得到**当 l 和 r 相等**就证明此时只有一个字符那么它的**返回值就是 1** 。
 *  如果传入的数组**只有两个字符即 l + 1 == r** 那么此时如果这两个字符**相等就返回 2** ，如果**不相等就返回 1** 。

**普遍情况：**

*  **两边的字符**都**不存在**于最长的回文子序列中。例：a1221b -> 1221;
 *  **右边的字符****不存在**在于最长的回文子序列中。例：1221b -> 1221;
 *  **左边的字符****不存在**在于最长的回文子序列中。例：a1221 -> 1221;
 *  **两边的字符**都**存在**于最长的回文子序列中。例：1w221 -> 1221。

此时代码就可以这样写：

//主函数
    public int longestPalindromeSubseq(String s) {
            char[] str = s.toCharArray();
            return maxString(str, 0, str.length-1);
    }
    
    //假设该函数可以返回最长回文子序列的长度
    public static int maxString(char[] str, int l, int r) {
            //先判断两种特殊情况
            if (l == r){
                return 1;
            }
            if (l + 1 == r){
                return str[l] == str[r] ? 2 : 1;
            }
            //余下的四种情况
            int a1 = maxString(str, l + 1, r - 1);
            int a2 = maxString(str, l, r - 1);
            int a3 = maxString(str, l + 1, r);
            int a4 = str[l] == str[r] ? 2 + maxString(str, l + 1, r - 1) : 0;
            
            //因为题目要求返回最长序列长度  所以需要返回这四个的最大值
            return Math.max(Math.max(a1, a2), Math.max(a3, a4));
    }

此时我们可以提交以下：

![f8c16927294843d7aff3bf74587f9066.png][]

虽然没通过但是从它的报错信息可以看出，我们的思路是没问题的。

# 动态规划： #

我们有了递归版本后就可以根据它来写出动态规划版本了。

因为在maxString() 方法中**只有 l 和 r 是变量**，而它们两个的**取值范围都是 \[0，str.length - 1\]**

此时我们就可以通过创建一个二维数组将 **l 和 r** 所有情况都列举出来然后返回**数组\[0，str.length - 1\] 下标的值**就可以得出答案了。

我们先假设长度只有 5 ，那么我们就可以创建如下的二维数组 **l 行，r 列**

public static int maxString(char[] str, int l, int r) {
    
            int[][] arr = new int[str.length][str.length];
            
    }

![0a7cd710ca9b47ad8b3ac6b0834d89d8.png][]

接下来的填表阶段就可以根据递归函数直接填（**以“a1221”为例子**）：

![e7f8453c0d5a4d2a887af027a2cfbdd7.png][]

![65e133fa5f6a4faa96980c144a741c65.png][]

此时 \[0， 4\] 位置的值就是最终答案。

根据每个位置的关系就将递归优化成：

public static int maxString(char[] str, int l, int r) {
    
            int[][] arr = new int[str.length][str.length];
            //因为不存在l < r的情况所以下三角的空间不用
            for (int i = 0; i < str.length; i++) {
                if (i == 0){//填第一条对角线
                    int j = 0;
                    while(j < str.length) {
                        arr[j][j] = 1;
                        j++;
                    }
                }else if (i == 1) {//填第二条斜线
                    int j = 1;
                    while(j < str.length) {
                        arr[j - 1][j] = (str[j - 1] == str[j]) ? 2 : 1;
                        j++;
                    }
                }else {//其他
                    int j = i;
                    int k = 0;
                    while(j < str.length){
                        int a1 = arr[k + 1][j - 1];
                        int a2 = arr[k][j - 1];
                        int a3 = arr[k + 1][j];
                        int a4 = str[k] == str[j] ? 2 + arr[k + 1][j - 1] : 0;
                        arr[k][j] = Math.max(Math.max(a1, a2), Math.max(a3, a4));
                        j++;
                        k++;
                    }
                }
    
            }
            return arr[0][str.length-1];
    }

此时再提交就过了。

![acbb597973d842949027935f9d08eede.png][]

[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[icon-default.png_t_N6B9_https_leetcode.cn_problems_longest-palindromic-subsequence_description_utm_source_LCUS_utm_medium_ip_redirect_utm_campaign_transfer2china]: https://leetcode.cn/problems/longest-palindromic-subsequence/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
[f8c16927294843d7aff3bf74587f9066.png]: https://img-blog.csdnimg.cn/f8c16927294843d7aff3bf74587f9066.png
[0a7cd710ca9b47ad8b3ac6b0834d89d8.png]: https://img-blog.csdnimg.cn/0a7cd710ca9b47ad8b3ac6b0834d89d8.png
[e7f8453c0d5a4d2a887af027a2cfbdd7.png]: https://img-blog.csdnimg.cn/e7f8453c0d5a4d2a887af027a2cfbdd7.png
[65e133fa5f6a4faa96980c144a741c65.png]: https://img-blog.csdnimg.cn/65e133fa5f6a4faa96980c144a741c65.png
[acbb597973d842949027935f9d08eede.png]: https://img-blog.csdnimg.cn/acbb597973d842949027935f9d08eede.png