友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
-
1 <= s.length <= 1000 -
s仅由小写英文字母组成
思路分析
最长的回文在哪里？当然是从字符串两头 (head, tail) 开始就是回文了。
-
如果
chars[head] == chars[tail]，那么往里搜索，找下一个匹配：chars[head+1] == chars[tail-1]。 -
如果
chars[head] != chars[tail]，那么最大回文字符可能存在于(head+1, tail)或者(head, tail-1)。
在推演转移方程时，一个很大的误区是从 dp 矩阵视角去看。因为这是处理字符串，从一维字符串字符坐标去看，会更加清楚明了。如下图：
根据代码流程来看，整个处理流程是从字符串的右边向左处理，相当于在“结尾”中寻找回文子串。所以，相关遍历只涉及的矩阵的左上方一半，从最下一行向上，逐行遍历。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-19 21:32:01
*/
public int longestPalindromeSubseq(String s) {
int length = s.length();
int[][] dp = new int[length][length];
for (int i = length - 1; i >= 0; i--) {
dp[i][i] = 1;
char ic = s.charAt(i);
for (int j = i + 1; j < length; j++) {
char jc = s.charAt(j);
if (ic == jc) {
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][length - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-24 21:35:23
*/
public int longestPalindromeSubseq(String s) {
char[] chars = s.toCharArray();
int length = s.length();
int[][] memo = new int[length][length];
int index = 0;
for (int[] ints : memo) {
Arrays.fill(ints, -1);
ints[index++] = 1;
}
return dfs(0, length - 1, chars, memo);
}
private int dfs(int i, int j, char[] chars, int[][] memo) {
if (i > j) {
return 0;
}
// if (i == j) {
// return 1;
// }
if (memo[i][j] != -1) {
return memo[i][j];
}
if (chars[i] == chars[j]) {
return memo[i][j] = dfs(i + 1, j - 1, chars, memo) + 2;
}
return memo[i][j] = Math.max(dfs(i + 1, j, chars, memo),
dfs(i, j - 1, chars, memo));
}
参考资料
-
516. 最长回文子序列 - 动态规划，四要素 — 该评论详细解释了如何处理奇偶回文的。