力扣-516-最长回文子序列

public int longestPalindromeSubseq(String s) {
    if(s == null || s.length() == 0)   return 0;
    char[] arr = s.toCharArray();
    int n = arr.length;

    int[][] dp = new int[n][n];//在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]
    for(int i = 0; i < n;i++){
        dp[i][i] = 1;
    }

    //反着遍历保证正确的状态转移
    for(int i = n-1;i>=0;i--){
        for(int j = i+1;j<n;j++){
            if(arr[i] == arr[j])
                dp[i][j] = dp[i+1][j-1] + 2;
            else
                dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);

        }
    }
    return dp[0][n-1];
}