LeetCode 516最长回文子序列 题目链接 https://leetcode.cn/problems/longest-palindromic-subsequence/ 题目概要给你一个字符串s找出其中最长的回文子序列并返回该序列的长度。子序列定义不要求字符连续在不改变原有字符顺序的前提下可以删除某些字符也可以不删除得到新字符串。回文定义正读和反读完全一致的字符串。示例示例 1输入s “bbbab”输出4解释一个可能的最长回文子序列为 “bbbb”。示例 2输入s “cbbd”输出2解释一个可能的最长回文子序列为 “bb”。约束条件1 s.length 1000s仅由小写英文字母组成 题目考点经典区间动态规划回文子序列 DP 模型与最长回文子串区分区间 DP 遍历顺序、状态转移逻辑考察字符串动态规划高频面试题 解题思路本题和「最长回文子串」不同子序列不要求连续因此解题思路采用标准区间 DP 求解。1. 状态定义定义二维dp数组dp[i][j]表示字符串区间s[i ... j]中最长回文子序列的长度。2. 初始状态单个字符一定是回文子序列长度为 1。因此初始化dp[i][i] 1所有对角线位置赋值为 1。3. 状态转移方程分两种情况讨论区间[i, j]两端字符相等s[i] s[j]两端字符可以同时加入回文序列结果为内部区间最长回文长度 2d p [ i ] [ j ] d p [ i 1 ] [ j − 1 ] 2 dp[i][j] dp[i1][j-1] 2dp[i][j]dp[i1][j−1]2两端字符不相等s[i] ! s[j]只能舍弃左端字符 或 舍弃右端字符取两种情况的最大值d p [ i ] [ j ] max ( d p [ i 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] \max(dp[i1][j], dp[i][j-1])dp[i][j]max(dp[i1][j],dp[i][j−1])4. 遍历顺序核心要点dp[i][j]的结果依赖于dp[i1][j-1]、dp[i1][j]、dp[i][j-1]也就是当前区间依赖更小的内层区间 / 下一行 / 前一列。因此遍历规则左边界i从后往前遍历从字符串末尾向开头右边界j从 i1 开始向后遍历保证区间长度由小到大5. 最终答案整个字符串对应区间[0, len-1]最终返回dp[0][len-1]。✅ AC 代码classSolution{publicintlongestPalindromeSubseq(Strings){char[]sss.toCharArray();intlens.length();int[][]dpnewint[len1][len1];// 初始化单个字符最长回文子序列长度为 1for(inti0;ilen;i){dp[i][i]1;}// 左边界从后往前遍历for(intilen-1;i0;i--){// 右边界从 i1 开始for(intji1;jlen;j){if(ss[i]ss[j]){// 两端字符相等内部结果 2dp[i][j]dp[i1][j-1]2;}else{// 两端不等取左右区间最大值dp[i][j]Math.max(dp[i1][j],dp[i][j-1]);}}}returndp[0][len-1];}}⏱️ 复杂度分析指标复杂度说明时间复杂度O ( n 2 ) O(n^2)O(n2)两层循环遍历所有区间n nn为字符串长度空间复杂度O ( n 2 ) O(n^2)O(n2)开辟二维 dp 数组存储区间状态 补充总结区分易混点最长回文子串连续、最长回文子序列不连续二者均常用区间 DP但状态转移逻辑不同。遍历顺序区间 DP 通用规律依赖内层子区间时左边界逆序遍历。基础边界单个字符回文长度固定为 1是 DP 初始化的关键。
LeetCode 516：最长回文子序列
LeetCode 516最长回文子序列 题目链接 https://leetcode.cn/problems/longest-palindromic-subsequence/ 题目概要给你一个字符串s找出其中最长的回文子序列并返回该序列的长度。子序列定义不要求字符连续在不改变原有字符顺序的前提下可以删除某些字符也可以不删除得到新字符串。回文定义正读和反读完全一致的字符串。示例示例 1输入s “bbbab”输出4解释一个可能的最长回文子序列为 “bbbb”。示例 2输入s “cbbd”输出2解释一个可能的最长回文子序列为 “bb”。约束条件1 s.length 1000s仅由小写英文字母组成 题目考点经典区间动态规划回文子序列 DP 模型与最长回文子串区分区间 DP 遍历顺序、状态转移逻辑考察字符串动态规划高频面试题 解题思路本题和「最长回文子串」不同子序列不要求连续因此解题思路采用标准区间 DP 求解。1. 状态定义定义二维dp数组dp[i][j]表示字符串区间s[i ... j]中最长回文子序列的长度。2. 初始状态单个字符一定是回文子序列长度为 1。因此初始化dp[i][i] 1所有对角线位置赋值为 1。3. 状态转移方程分两种情况讨论区间[i, j]两端字符相等s[i] s[j]两端字符可以同时加入回文序列结果为内部区间最长回文长度 2d p [ i ] [ j ] d p [ i 1 ] [ j − 1 ] 2 dp[i][j] dp[i1][j-1] 2dp[i][j]dp[i1][j−1]2两端字符不相等s[i] ! s[j]只能舍弃左端字符 或 舍弃右端字符取两种情况的最大值d p [ i ] [ j ] max ( d p [ i 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] \max(dp[i1][j], dp[i][j-1])dp[i][j]max(dp[i1][j],dp[i][j−1])4. 遍历顺序核心要点dp[i][j]的结果依赖于dp[i1][j-1]、dp[i1][j]、dp[i][j-1]也就是当前区间依赖更小的内层区间 / 下一行 / 前一列。因此遍历规则左边界i从后往前遍历从字符串末尾向开头右边界j从 i1 开始向后遍历保证区间长度由小到大5. 最终答案整个字符串对应区间[0, len-1]最终返回dp[0][len-1]。✅ AC 代码classSolution{publicintlongestPalindromeSubseq(Strings){char[]sss.toCharArray();intlens.length();int[][]dpnewint[len1][len1];// 初始化单个字符最长回文子序列长度为 1for(inti0;ilen;i){dp[i][i]1;}// 左边界从后往前遍历for(intilen-1;i0;i--){// 右边界从 i1 开始for(intji1;jlen;j){if(ss[i]ss[j]){// 两端字符相等内部结果 2dp[i][j]dp[i1][j-1]2;}else{// 两端不等取左右区间最大值dp[i][j]Math.max(dp[i1][j],dp[i][j-1]);}}}returndp[0][len-1];}}⏱️ 复杂度分析指标复杂度说明时间复杂度O ( n 2 ) O(n^2)O(n2)两层循环遍历所有区间n nn为字符串长度空间复杂度O ( n 2 ) O(n^2)O(n2)开辟二维 dp 数组存储区间状态 补充总结区分易混点最长回文子串连续、最长回文子序列不连续二者均常用区间 DP但状态转移逻辑不同。遍历顺序区间 DP 通用规律依赖内层子区间时左边界逆序遍历。基础边界单个字符回文长度固定为 1是 DP 初始化的关键。
