516. 最长回文子序列（动态规划）

秒速五厘米 2023-10-05 19:27 23阅读 0赞

#### 516. 最长回文子序列 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

两种思路：  
1、第一种思路模板是一个一维的 dp 数组（用在本题比较复杂）：

> 写过的例子「最长递增子序列」，在这个思路中 dp 数组的定义是：在子数组 array\[0…i\] 中，我们要求的子序列（最长递增子序列）的长度是 dp\[i\]。

2、第二种思路模板是一个二维的 dp 数组（本题采用）：

**对 dp 数组的定义是：在子串 s\[i…j\] 中，最长回文子序列的长度为 dp\[i\]\[j\]**  
按照这个思路，那么我们的最终结果是求`s[0,...,(s.length-1)]`，所以最后的dp应该是`dp[0][s.length-1]`。这时候我们就可以构建起来二维dp的图了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

现在来解释一下：  
①对角线全是1，即最长回文子序列长度为1。这是因为**base case**，只有一个字符，那么子串s\[i…j\]中`i=j=1。`

②对角线左下方全是0，因为左下方是i>j，这根本不可能，我们一定要保证i<=j

③为什么是倒着遍历？因为我们最终要返回的结果是`dp[0][s.length-1]`，是在图中的左上角，那么我们就需要朝着目标去遍历

④循环中`i=n-2`，`j=i+1`是为什么？看图。倒着遍历，第一个遍历的空白格子的下标就是初始的`i、j`

## 代码 ##

class Solution {
        
        public int longestPalindromeSubseq(String s) {
        
            //dp数组的定义：在字串S[i..j]中，最长回文子序列的长度为dp[i][j]
    
            int n=s.length();
            int[][] dp=new int[n][n];//默认数组值全为0
    
            //base case
            for(int i=0;i<n;i++){
        
                dp[i][i]=1;//只有一个字符，子串s[i..j]中 i==j==1。
            }
    
            for(int i=n-2;i>=0;i--){
        //结合dp表来看i=n-2，就可以理解
                for(int j=i+1;j<n;j++){
        
                    if(s.charAt(i)==s.charAt(j)){
        
                        /*如果它俩相等，那么s[i...j]的最长回文子序列长度就等于它俩的长度2加                         上，s[i+1,....,j-1]中的最长回文子序列长度。
                        */
                        dp[i][j]=dp[i+1][j-1]+2;
                    }else{
        
                        /*如果它俩不等，那么它俩不可能同时出现在s[i..j]的最长回文子序列中，
                        只需要把它俩分别加入到s[i+1,...,j-1]中，看谁产生的回文串更长
                        */
                        dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                    }
                }
            }
            return dp[0][n-1];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210207231637590.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210207232152321.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70