1、前言

2、思路

定义一个二维数组 dp[i][j]，表示：在子串 s[i ... j] 中，最长回文字串的长度为 dp[i][j]。

关于 dp[i][j] 的递推状态：在 dp[i + 1][j - 1] 时，s[i] == s[j]，那么加上这两个字符即可（加2）；如果 s[i] != s[j]，那么就分别加上一个字符，看哪个最大，即 max{ dp[i][j - 1], dp[i + 1][j] }。

关于 base case：因为 i 不可能大于 j，所以 i 大于 j 的地方都是 0；如果 i == j，那么说明字符只有一个，那么此时都是 1；我们最终是求 dp[0][n - 1]（n 是字符串的长度）。

然后就是遍历方式，这道题可以画出一个二维数组，发现只能反着或者斜着遍历才能从已知递推到未知。

但是这道题一个终极最简单的方法：利用两个字符串的最长公共子序列来做。我们可以将原字符串 s 反转成 k，然后求 s 和 k 的最长公共子序列，这个子序列就是最长回文子序列。

3、代码

public class LongestPalindromeSubseq {

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

        for(int i = 0; i < m; i++){
            dp[i][i] = 1;
        }


        // 为什么要反向遍历，已经二维表是由已知推未知，
        // 只有这种方式才能满足根据旁边三个角的值推到最终值
        for(int i = m - 1; i >= 0; i--){
            for(int j = i + 1; j < m; 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][m - 1];
    }

    /**
     * 使用两个数组最长子序列的思路，先将 s 反转成 k，然后求 s 和 k 的子序列
     * @param s
     * @return
     */
    public int longestPalindromeSubseq2(String s) {
        int m = s.length();
        int[][] dp = new int[m + 1][m + 1];
        String k = new StringBuilder(s).reverse().toString();

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= m; j++){
                if(s.charAt(i - 1) == k.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][m];
    }

    public static void main(String[] args) {
        String s = "bbbab";
        System.out.println(new LongestPalindromeSubseq().longestPalindromeSubseq2(s));
    }
}