题目

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

题解

动态规划法

思路

所谓的动态规划，即为把问题转化为求子问题，不断的进行状态的转移，最终收敛于一个已知的初始条件。

1. 首先常规思路，暴力解法，不删减字符的情况下，通过枚举所以的子串，就可以找出最长回文子串。
   但是题目是说可以通过删减某字符来求最长回文子串，这个就算暴力解也不好解了，如示例1所示，可以把a删掉，求得最长回文子串”bbbb“（并不是s的原始子串）
2. 动态规范法
   i和j位置的左右指针i和j，i从字符串右边界开始遍历，不断往左遍历，i的每次位置的固定后，j从i+1位置开始遍历至右边界。
   那么问题[i,j]范围的最长回文子串问题就变成了其范围内子串的最长回文子串问题，逻辑层面是大问题不断的收敛于子问题，但求解过程是从最小边界子问题往大问题扩散求解。
   需要遍历i和j两个条件，因此假设有二维数组subLen[n][n]，subLen[i][j]为[i,j]范围的最长回文子串长度。
   • 0<=i<j<n范围内，也就是在字符串s范围内的左右指针i和j条件下，才有subLen[i][j]>0，也就是说超出s的范围或者左右指针颠倒，就超出了枚举的范围和意义，其最长回文子串长度都是0。
     可以想象为，二维数组的(0,0)、(n-1，n-1)对角线的又上部分的值都是0。
   • 状态转移
     i和j位置的字符相同，那么转化为小问题就是[i+1，j-1]范围的最长回文子串长度+2，因为i和j位置字符相同，那么[i,j]范围的最长回文子串的最长长度至少是2；
     i和j位置的字符不同，那么转化为小问题就是：[i，j]范围的最长子串枚举，注意不是最长回文子串，有[i+1，j]、[i，j-1]，那么小问题是，[i+1，j]范围最长回文子串长度和[i，j-1]范围最长回文子串长度的最大值。

代码

    private static int longestPalindromeSubseq(String s) {
        int n = s.length();
        // 要点1：初始化为0（0<=i<j<n时subLen[i][j] > 0，否则等于0
        int[][] subLen = new int[n][n];
        // 要点2：从右边界开始遍历，动态规划的状态转移是从短子串向长子串转移
        for (int i = n - 1; i >= 0; i--) {
            // 要点3：一个字符的子串的回文长度是1，动态规划的边界初始值
            subLen[i][i] = 1;
            char charAti = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                if (charAti == s.charAt(j)) {
                    // 要点4：如果i和j位置字符相同，那不管其中间区域最长回文子串长度是几，假设为m，[i,j]范围最长回文子串长度为m+2
                    subLen[i][j] = subLen[i + 1][j - 1] + 2;
                } else {
                    // 要点5：如果i和j位置字符不相同，[i,j]范围的最长子串枚举为：[i+1,j]、[i,j-1],[i,j]范围最长回文子串长度为max([i+1,j]最长回文,[i,j-1]最长回文)
                    subLen[i][j] = Math.max(subLen[i + 1][j], subLen[i][j - 1]);
                }
            }
        }
        // 要点6：最终的结果是[0,n-1]范围的最长回文子串长度，也就是字符串s的最长回文子串长度，值为subLen[0][n - 1]的值
        return subLen[0][n - 1];
    }

github