最长回文子序列Longest Palindromic Subsequence四种动态规划解法详解LeetCode 516 从中心扩展到 LCS 归约【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文系统讲解 LeetCode 516「最长回文子序列」Longest Palindromic Subsequence的完整解题体系覆盖自顶向下记忆化中心扩展、自顶向下记忆化区间收缩、转化为最长公共子序列LCS与自底向上空间优化四种思路并逐一给出可直接运行的代码、递推推导与复杂度分析。读完本文你将不仅能 AC 本题还能把「回文类区间 DP」和「字符串反转归约 LCS」这两类经典套路迁移到其他序列问题上。仓库中本题目录下收录了多语言实现本文所有代码与仓库源码相互印证。前置知识在动手解决该问题前建议先熟练掌握以下四个基础点这也是本仓库该题文档 articles/longest-palindromic-subsequence.md 明确列出的前提二维动态规划2D DP本题需要一个二维 DP 表用两个下标子串左端点i、右端点j来记录回文长度是典型的区间 DP 结构递归 记忆化Recursion with Memoization自顶向下方案通过带缓存的递归调用避免重复计算相同子问题最长公共子序列LCS解法三把原问题归约为「字符串与自身反转串的 LCS」因此需要先掌握经典 LCS 的 DP 递推字符串操作String Manipulation涉及子串/子序列的索引处理与字符比较。问题定义子序列 ≠ 子串给定一个字符串s求其最长回文子序列的长度。子序列是从原串中按顺序、但不要求连续地取出若干字符组成的序列而子串要求连续。以bbbab为例最长回文子序列是bbbb长度为 4可以跳过中间的a最长回文子串是bbb长度为 3。因此求解时必须允许跳过字符——这正是「子序列」与「子串」问题的本质区别也是下文所有 DP 递推中「不匹配时二选一取 max」这一分支的来源。解法一自顶向下记忆化中心扩展核心直觉回文正读反读相同因此可以想象从中心向外扩张来构造回文每个可能的中心奇数长度回文对应单个字符偶数长度回文对应两个字符之间的缝隙都尝试向外扩展检查两侧字符是否相等若两侧字符相等则把两侧都纳入子序列继续向外扩展若不相等则有两条路可选跳过左侧字符或跳过右侧字符取两者中较长的结果。用记忆化缓存已经算过的子问题避免重复计算。算法步骤建立二维记忆化表dp其中dp[i][j]表示「从下标i向左扩展、从下标j向右扩展时能形成的以i、j为最外层的最大回文子序列长度」定义递归函数dfs(i, j)若i 0或j n越界返回0若已计算过直接返回缓存值若s[i] s[j]则累加1i j同一个字符或2i ! j两个不同字符再加上向两侧继续扩展的结果dfs(i-1, j1)否则取max(dfs(i-1, j), dfs(i, j1))——跳过左侧或右侧字符对所有可能的中心调用dfs奇数长度中心为dfs(i, i)偶数长度中心为dfs(i, i1)返回 DP 表中所有已计算状态的最大值。代码实现Pythonclass Solution: def longestPalindromeSubseq(self, s: str) - int: n len(s) dp [[-1] * n for _ in range(n)] def dfs(i, j): if i 0 or j n: return 0 if dp[i][j] ! -1: return dp[i][j] if s[i] s[j]: length 1 if i j else 2 dp[i][j] length dfs(i - 1, j 1) else: dp[i][j] max(dfs(i - 1, j), dfs(i, j 1)) return dp[i][j] for i in range(n): dfs(i, i) # odd length 奇数长度中心 dfs(i, i 1) # even length 偶数长度中心 return max(max(row) for row in dp if row ! -1)复杂度分析时间复杂度$O(n^2)$ —— 最多有 $n^2$ 个(i, j)状态每个状态 $O(1)$ 转移空间复杂度$O(n^2)$ —— 二维记忆化表。仓库佐证这一「中心扩展 记忆化」的写法在仓库 Python 实现 python/0516-longest-palindromic-subsequence.py 中以cache 闭包dfs(i, j)的形式完整出现并显式注释了odd length/even length两种中心。解法二自顶向下记忆化区间向内收缩核心直觉与解法一「从中心向外扩张」相反解法二从完整字符串开始向内收缩。把子问题定义为子串s[i..j]内的最长回文子序列长度。当首尾字符相等时两者可以同时纳入回文于是答案 内部子串的解 2当首尾字符不等时两者中必有一个不在最长回文里于是分别尝试排除左端或右端取较优者。这种视角与解法一方向相反但递推结构同样干净且只需要一次dfs(0, n-1)调用逻辑上更直观。算法步骤创建记忆化缓存哈希表或二维数组存放已计算结果定义递归函数dfs(i, j)若i j空子串返回0若i j单字符返回1——单字符天然是长度为 1 的回文若已缓存直接返回若s[i] s[j]返回2 dfs(i1, j-1)否则返回max(dfs(i1, j), dfs(i, j-1))调用dfs(0, n-1)得到整个字符串的答案。代码实现Pythonclass Solution: def longestPalindromeSubseq(self, s: str) - int: cache {} def dfs(i, j): if i j: return 0 if i j: return 1 if (i, j) in cache: return cache[(i, j)] if s[i] s[j]: cache[(i, j)] dfs(i 1, j - 1) 2 else: cache[(i, j)] max(dfs(i 1, j), dfs(i, j - 1)) return cache[(i, j)] return dfs(0, len(s) - 1)复杂度分析时间复杂度$O(n^2)$空间复杂度$O(n^2)$。两种自顶向下方案可相互印证解法一是「向外扩」解法二是「向内缩」。在实现上解法二由于只调用一次dfs(0, n-1)不需要像解法一那样遍历所有中心代码更简洁。解法三转化为最长公共子序列LCS核心直觉一个非常巧妙的观察字符串的最长回文子序列 该字符串与其反转字符串的最长公共子序列LCS。为什么成立任何回文子序列正读反读顺序一致因此它必然是「原串」与「反转串」的公共子序列反之原串与反转串的任何公共子序列都对应回文。于是问题被归约为教科书级的经典 LCS 问题直接用现成的二维 DP 模板求解即可。算法步骤构造输入字符串的反转串套用标准 LCS 算法建立二维 DP 表dp[i][j]表示「原串前i个字符」与「反转串前j个字符」的 LCS 长度若s1[i] s2[j]则dp[i1][j1] dp[i][j] 1否则dp[i1][j1] max(dp[i1][j], dp[i][j1])返回dp[n][n]作为最终答案。代码实现Pythonclass Solution: def longestPalindromeSubseq(self, s: str) - int: return self.longestCommonSubsequence(s, s[::-1]) def longestCommonSubsequence(self, s1: str, s2: str) - int: N, M len(s1), len(s2) dp [[0] * (M 1) for _ in range(N 1)] for i in range(N): for j in range(M): if s1[i] s2[j]: dp[i 1][j 1] 1 dp[i][j] else: dp[i 1][j 1] max(dp[i 1][j], dp[i][j 1]) return dp[N][M]复杂度分析时间复杂度$O(n^2)$空间复杂度$O(n^2)$。仓库佐证本仓库的 Kotlin 实现 kotlin/0516-longest-palindromic-subsequence.kt 正是采用此思路——s1.reversed()构造反转串再用dp[i1][j1]的标准 LCS 递推表求解Python 实现 python/0516-longest-palindromic-subsequence.py 中也独立收录了这份longestCommonSubsequence(s, s[::-1])解法与本文解法三完全一致。解法四自底向上空间优化O(n) 空间核心直觉自底向上填表时每个格子的值只依赖当前行的相邻格与上一行的某个格在本公式下是「当前行左侧」与「前一行的对角值」。只要按正确的顺序处理并只保留必要的历史值就能把空间从 $O(n^2)$ 压缩到 $O(n)$。算法步骤创建长度为n的一维 DP 数组dp外层循环i从n-1递减到0令dp[i] 1单个字符构成回文用prev记录「上一轮的斜对角值」内层循环j从i1到n-1先用temp保存当前dp[j]更新前若s[i] s[j]则dp[j] prev 2否则dp[j] max(dp[j], dp[j-1])最后prev temp完成对角值的滚动返回dp[n-1]。代码实现Pythonclass Solution: def longestPalindromeSubseq(self, s: str) - int: n len(s) dp [0] * n for i in range(n - 1, -1, -1): dp[i] 1 prev 0 for j in range(i 1, n): temp dp[j] if s[i] s[j]: dp[j] prev 2 else: dp[j] max(dp[j], dp[j - 1]) prev temp return dp[n - 1]复杂度分析时间复杂度$O(n^2)$空间复杂度$O(n)$。仓库佐证Swift 实现 swift/0516-longest-palindromic-subsequence.swift 是这一思路的变体——它用两个一维数组dp与dpPrev滚动保存「当前行」与「上一行」同样把空间压缩到 $O(n)$当s[i] s[j]时取dpPrev[j-1] 2上一行对角否则取max(dpPrev[j], dp[j-1])。对比两版代码可以加深对「行间依赖」的理解。多语言实现索引原题文档 articles/longest-palindromic-subsequence.md 为上述四种解法都提供了Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust九种语言的 tab 切换实现语言层面的差异点在于Rust中将字符串转成s.as_bytes()的字节切片用isize/usize分别处理i可能为负解法一与j非负的索引类型问题Go需要手写max辅助函数Go 1.21 前标准库无泛型maxSwift先把字符串转成Array(s)字符数组避免 String 下标访问的复杂度开销Kotlin借助s.reversed()一行构造反转串解法三。在仓库中本题在 README.md 的收录表中标记了 Python 与 Kotlin 两门语言已提交✔️对应文件即上文提到的 python/0516-longest-palindromic-subsequence.py 与 kotlin/0516-longest-palindromic-subsequence.kt。常见陷阱陷阱一混淆子序列与子串子序列不要求连续子串要求连续。对bbbab最长回文子序列是bbbb长度 4而最长回文子串是bbb长度 3。若你的解法不允许「跳过字符」就会退化成子串问题答案错误。务必保证在不匹配分支中允许跳过任意一侧的字符。陷阱二基础情形Base Case处理错误递归或 DP 实现中常见的 off-by-one 错误源于基础情形单字符i j永远是长度为 1 的回文必须返回1空区间i j长度为0忘记给单字符返回1或初始化 DP 表时初值不当都会导致结果偏小或数组越界。陷阱三自底向上 DP 的遍历顺序错误自底向上填表必须保证小子问题先于大子问题求解外层i应从n-1递减到0内层j应从i递增到n-1在解法四中内层从i1开始。若方向反了算法会读取尚未计算的值产生错误结果。这一顺序约束正是解法四中prev对角值滚动逻辑成立的前提。四种解法速查对比解法思路方向递推要点时间复杂度空间复杂度一自顶向下中心扩展从中心向外扩相等则长度 dfs(i-1, j1)不等则取max(dfs(i-1, j), dfs(i, j1))$O(n^2)$$O(n^2)$二自顶向下区间收缩从两端向内缩相等则2 dfs(i1, j-1)不等则取max(dfs(i1, j), dfs(i, j-1))$O(n^2)$$O(n^2)$三归约 LCS原串 vs 反转串s[i]s[j]则dp[i1][j1]dp[i][j]1否则取 max$O(n^2)$$O(n^2)$四自底向上空间优化区间 DP 滚动数组dp[j] prev 2或max(dp[j], dp[j-1])$O(n^2)$$O(n)$选型建议面试或比赛中解法二区间收缩代码最直观、最不易出错解法三LCS 归约适合作为「发现本质」的加分讲解且能复用现成的 LCS 模板解法四则在输入规模较大、内存受限时是必须掌握的优化版本。四者时间均为 $O(n^2)$最终答案统一由整个 DP 表或滚动数组末尾的最大值给出。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考