516. 最长回文子序列 (opens new window)

1.动态规划+长度继承

定义dp[i][j]表示子串 i 到 j 之间含有的最长回文序列长度。更新时包含以下几种情况：

• 如果左端点 i 或者右端点 j 都没有构成新的回文子序列，当前最长回文子序列等于两者之间的最大值，继承前面已经搜索得到的长度。
• 如果当前首尾元素相同，那么它们构成的新回文子序列长度等于夹层部分构成回文子序列长度加上两个端点元素的长度和，即dp[i+1][j-1]+2

✨子序列的动规算法中，往往都需要把前面搜索过的子序列长度的结果继承给当前子序列。由于子序列具有不连续性，因此并不是所有子序列状态的值都与当前端点有关。

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