大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。

1-1：题目

Given a string s, find the longest palindromic subsequence’s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence

1-2：idea

这道题主要和Java描述 LeetCode，647. Palindromic Substrings 回文子串，这道题形成鲜明的对比，解题思路是差不多的，唯一的区别就是647题是回文子串，就是说必须是连续的，这里的516题是子序列，可以不连续的。有了上一题的经验，我们很容易想到dp状态。

• dp状态：dp[i][j]：s[i:j]（左包含右包含）的最长回文子序列的长度是dp[i][j]。
• 状态转移方程：
  • s[i] == s[j]，往里缩，dp[i][j] = dp[i+1][j-1] + 2;+2是因为s[i],s[j]两个相等的字符要算上的，这样得到新的最优解。
  • s[i] != s[j]，两种手段，i往里面缩或者j往里面缩，取最大值， dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])，为什么647题不相等就不用继续考虑呢？因为647题要求是连续的回文子串，不相等了i,j再往里面考虑没有意义了，但这边不一样，这里是可以不连续的，可以继续往里面考虑。这边不理解可以先看看上面的647题，两道题对比起来做，会很好。
• 遍历顺序：从下往上，从左到右。和647一样。
• 初始化：这里根据状态转移方程，可以对i == j的部分初始化，也就是打表时候的斜对角。

1-3：代码

public static int longestPalindromeSubseq(String s) {
   int n = s.length();

   int[][] dp = new int[n][n]; // 0~n-1

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

   for (int i = n - 2; i >= 0; i--) {
       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 + 1][j], dp[i][j - 1]);
           }
       }
   }
   System.out.println(Arrays.deepToString(dp));
   return dp[0][n - 1];
}

同样要注意，i<=j 这个是整个代码中必须要注意到的，斜对角的左下方是不用考虑的。（这里和647题是一样的）

1-4：代码小优化

上面的代码其实不够完美，我们可以把初始化放进外侧循环，一边遍历一遍初始化。还有一个优化点，就是s.charAt(i)，其实可以放到外侧循环，提前保存好，这样就不用每次内循环去做s.charAt(i)这个操作了，这个也是一个小优化点。

优化代码如下：

public static int longestPalindromeSubseq2(String s) {
    int n = s.length();

    int[][] dp = new int[n][n]; // 0~n-1

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

打表：
String s = "bbbab";

\ j 0  1  2  3  4
i \ b  b  b  a  b
0 b[1, 2, 3, 3, 4]
1 b[0, 1, 2, 2, 3]
2 b[0, 0, 1, 1, 3]
3 a[0, 0, 0, 1, 1]
4 b[0, 0, 0, 0, 1]

1-5：总结

这道题主要和647对比起来，属于差不多的题，只是一个是子序列（不连续），一个是子串（连续），如果你做了647题，这里总的来说难度不是很大。继续加油！！河海哥，冲！至少做到，做过的以后能写出来。💪您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。