516. 最长回文子序列

image.png

子串代表连续，子序列不代表连续
求子串利用左右指针，求子序列需要利用动态规划
其中dp[i][j]代表从i到j的字符
从倒数第二个字符开始遍历字符串，i
j=i+1,遍历到字符串结尾
1：如果s.charAt(i)==s.charAt(j)，说明dp[i][j]=dp[i+1][j-1]+2;

image.png

2：如果不相等，dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j])

image.png
从右下角一直对矩阵进行填充
image.png

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