529，动态规划解最长回文子序列

Original 博哥数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

You may be out, but you never lose the attitude.

人可以受挫，但精神不可以倒下。

问题描述

给定一个字符串s，找到其中最长的回文子序列，并返回该序列的长度。可以假设s的最大长度为 1000 。

示例 1:
输入:

"bbbab"

输出:

4

一个可能的最长回文子序列为 "bbbb"。

示例 2:
输入:

"cbbd"

输出:

2

一个可能的最长回文子序列为 "bb"。

提示：

1 <= s.length <= 1000
s 只包含小写英文字母

动态规划解决

注意这里是求最长回文子序列不是回文子串，子串必须是连续的，但子序列不一定是连续的。

我们定义dp[i][j]表示字符串中从i到j之间的最长回文子序列。

1，如果s.charAt(i) == s.charAt(j)，也就是说两头的字符是一样的，他们可以和中间的最长回文子序列构成一个更长的回文子序列，即

dp[i][j]=dp[i+1][j-1]+2

如下图所示

2，如果s.charAt(i) != s.charAt(j)，说明i和j指向的字符是不相等的，我们可以截取，要么去掉i指向的字符，要么去掉j指向的字符，然后取最大值，即

dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])

如下图所示

有了递推公式，我们再来看下Base case，就是一个字符也是回文串，即dp[i][i]=1；

注意二维数组dp[i][j]的定义，如果i>j是没有意义的。再来看一下他们之间的关系

从上面图中可以看出如果我们想求dp[i][j]，那么其他3个必须都是已知的，很明显从上往下遍历是不行的，我们只能让i从最后一个字符往前遍历，j从i的下一个开始遍历，最后只需要返回dp[0][length - 1]即可。来看下代码

 1public int longestPalindromeSubseq(String s) {
 2    int length = s.length();
 3    int[][] dp = new int[length][length];
 4    //这里i要从最后一个开始遍历
 5    for (int i = length - 1; i >= 0; i--) {
 6        //单个字符也是一个回文串
 7        dp[i][i] = 1;
 8        //j从i的下一个开始
 9        for (int j = i + 1; j < length; j++) {
10            //下面是递推公式
11            if (s.charAt(i) == s.charAt(j)) {
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][length - 1];
19}