题目描述

image.png

解题思路

dp

  • dp含义

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

  • 确定递推公式

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。
如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
image.png
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

  • 加入s[j]的回文子序列长度为dp[i + 1][j]。
  • 加入s[i]的回文子序列长度为dp[i][j - 1]。
  • 那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

image.png

  • 初始化

由递推公式可以知道，是无法递推到i=j的情况，所以需要手动初始化，当i==j时，此时回文字串长度为1。

  • 遍历顺序

和上一题一样，从下到上，从左到右。

  • 举例推导dp数组

输入s:”cbbd” 为例，dp数组状态如图：
image.png
红色框即：dp[0][s.size() - 1]; 为最终结果。

  1. public int longestPalindromeSubseq(String s) {
  2.     // dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
  3.     int[][] dp = new int[s.length()][s.length()];
  4.     for (int i = 0; i < s.length(); i++) {
  5.         dp[i][i] = 1;   // dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。所以计算的时候一个单词就是回文子序列的长度为1.
  6.     }
  8.     for (int i = s.length() - 1; i >= 0; i--) { // 从下到上遍历
  9.         for (int j = i + 1; j < s.length(); j++) {  // j的开始位置要和回文子串区别，因为此时不能计算单独的字符串，最少需要2个字符，否则地推公式失效
  10.             if (s.charAt(i) == s.charAt(j)) {
  11.                 // 如果两个区间的边上的字母相等，那么就是他们相隔区间的子序列最大值加二
  12.                 dp[i][j] = dp[i + 1][j - 1] + 2;
  13.             } else {
  14.                 // 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
  15.                 dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
  16.             }
  17.         }
  18.     }
  20.     return dp[0][s.length() - 1];   // 最终就是整个串的最大子序列
  21. }