516.Longest Palindromic Subsequence

1-Dp

dp[i][j]: the longest palindromic subsequence's length of substring(i, j)
State transition:
dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
Initialization: dp[i][i] = 1

这道题考的是最长回文子序列，注意是序列而不是子串，序列的意思是组成回文的字符可以是不连续的，而回文子串则需要连续的，比如例子中的bbbab，最长回文序列是bbbb，最长回文子串是bbb或是bab。

当已知一个序列是回文时，添加首尾元素后的序列存在两种情况，一种是首尾元素相等，则最长回文的长度加2，当首尾元素不相等，则最长回文序列为仅添加首元素时的最长回文与仅添加尾元素时的最长回文之间的最大值。我们可以用dp[i][j]表示s[i…j]中的最长回文序列，而状态转移方程则是 
1. i > j，dp[i][j] = 0； 
2. i == j，dp[i][j] = 1； 
3. i < j且s[i] == s[j]，dp[i][j] = dp[i + 1][j - 1] + 2； 
4. i < j且s[i]！= s[j]，dp[i][j] = max(dp[i + 1][j]，dp[i][j - 1])；

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i = n - 1; i >= 0; i--){
            dp[i][i] = 1;
            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];
    }
}