代码随想录动态规划——最长回文子序列

题目

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

示例 1: 输入: “bbbab” 输出: 4 一个可能的最长回文子序列为 “bbbb”。

示例 2: 输入:“cbbd” 输出: 2 一个可能的最长回文子序列为 “bb”。

提示：

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

思路

首先明白两个的区别

• 回文子串是要连续的
• 回文子序列可以不连续

动规五部曲：

1. 确定dp数组和下标含义
   dp[i][j]表示字符串s在区间[i，j]内的最长的回文子序列的长度

2. 确定递推公式
   判断回文字串，关键就是看s[i]与s[j]是否相同
   （1）如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
   从两端往中间判断：
   
   （2）如果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])
   

3. 初始化dp数组

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况

所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1

其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖

4. 确定遍历顺序
   从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]和dp[i][j - 1]，所以遍历i要从上到下

5. 举例推导dp数组
   输入s:“cbbd” 为例，dp数组状态如图：
   
   java代码如下：

class Solution {
	public int longestPalindromeSubseq(String s){
		int len = s.length();
		int[][] dp = new  int[len + 1][len + 1];
		for(int i = len - 1; i >= 0; i--){// 从后往前遍历 保证情况不漏
			dp[i][i] = 1;//初始化
			for(int j = i + 1; j < len; 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]);
				}
			}
		}
		//最后返回所有数的最长回文数,就是起始值为0,最终值为s.length()-1的下标的最长回文数
		return dp[0][len-1];//不理解的话重新看下dp[i][j]的定义，表示的就是区间[i，j]的回文子串的最大长度
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

另一种思路：也可以用最长公共子序列来做，因为s与s.reverse()的最长公共子序列即为其最长回文子序列