image.png
    解题思路：回文型的动态规划问题，其DP的推导依赖于这样一个原则：假设s[i, ..., j]是一个回文子序列，那么去除首位两端的字符，即s[i+1, ..., j-1]仍为一个回文子序列。
    所以，DP的定义：dp[i][j] 表示 s[i, ..., j]中最长的回文子序列长度。
    假设s的长度为 n，仅当 0 <= i < j < n 时，dp[i][j] = 1，否则为0（意味着 dp[3][2] 这样的是不合法的状态）。
    DP方程的转移需要依赖首尾两端的字符，即s[i]和s[j]，有以下两种情况：

    • case1：当s[i] == s[j]时，dp[i][j] = dp[i+1][j-1] + 2。
    • case2：当s[i] != s[j]时，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

    注：在计算DP时，需要考虑计算顺序，在上面的转移方程中，我们可以看到dp[i][] 依赖于 dp[i+1][]，所以第一维的计算顺序是逆序的（即i从大到小），第二维是顺序的。
    考虑初始化问题，当子序列长度为1时，必然是回文子序列，所以有dp[i][i]=1。
    最后，dp[0][n-1]即为我们所求。

    • 时间复杂度：O(n * n)

    • 空间复杂度：O(n * n)

      1. class Solution {
      2.   public int longestPalindromeSubseq(String s) {
      3.       int n = s.length();
      4.       int[][] dp = new int[n][n];
      6.       for(int i = n - 1; i >= 0; i--){
      7.           dp[i][i] = 1;
      8.           char ch1 = s.charAt(i);
      9.           for(int j = i + 1; j < n; j++){
      10.               char ch2 = s.charAt(j);
      11.               if(ch1 == ch2){
      12.                   dp[i][j] = dp[i + 1][j - 1] + 2;
      13.               }else{
      14.                   dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      15.               }
      16.           }
      17.       }
      18.       return dp[0][n - 1];
      19.   }
      20. }