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

516. 最长回文子序列

• 题目
• 解题思路
• 代码

题目

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

解题思路

两种思路：
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的图了。

现在来解释一下：
①对角线全是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];
    }
}