友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
-
1 <= s.length <= 1000 -
s仅由小写英文字母组成
思路分析
在推演转移方程时，一个很大的误区是从 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];
}
参考资料
-
516. 最长回文子序列 - 动态规划，四要素 — 该评论详细解释了如何处理奇偶回文的。