Longest Palindromic Subsequence

此题就是经典的最长对称字串的变体，这里字串变成了子序列，而子序列的转移方程就可以参考LCS了，实际上这里最容易想到的也就是反转输入字符串，然后再对这两个字符串找LCS就是我们需要的结果了

public class Solution {
    public int longestPalindromeSubseq(String s) {
        String k = new StringBuilder(s).reverse().toString();
        return LCS(s, k, k.length());
    }

    public int LCS(String A, String B, int n) {
        int[][] ref = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                ref[i][j] = 0;
            }
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    ref[i][j] = ref[i - 1][j - 1] + 1;
                } else {
                    ref[i][j] = Math.max(ref[i - 1][j], ref[i][j - 1]);
                }
            }
        }

        return ref[n][n];
    }
}

上面这种方法实际上偷换了概念把问题转换成了求LCS，而如果非要我们用类似最长对称子串的思维来做呢？一样可以，还是利用和对称子串的DP方法一样的思维，逐列往前推，且每个字符本身就是一个对称序列，这样转移方程变成了

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) if s[i] != s[j]
dp[i][j] = dp[i - 1][j - 1] if s[i] == s[j]

这里能看出和LCS的转移方程很相似了，两个字符的base case没有囊括进去，另外我们要求的结果也同样是dp[0][n - 1]，这也是区间类DP的明显标志

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) { 
                if (i == j) {
                    dp[j][i] = 1;
                } else if (j + 1 == i) {
                    if (s.charAt(j) == s.charAt(i)) {
                        dp[j][i] = 2;
                    } else {
                        dp[j][i] = 1;
                    }
                } else if (s.charAt(j) != s.charAt(i)) {
                    dp[j][i] = Math.max(dp[j + 1][i], dp[j][i - 1]);
                } else {
                    dp[j][i] = dp[j + 1][i - 1] + 2;
                }
            }
        }

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

另外此题Python怎么写都不能过也是无语...