What is the key pattern for solving Longest Palindromic Subsequence?

State transition dynamic programming is the core pattern; use dp[i][j] to track longest palindromic subsequences in substrings.

Can this problem be solved with recursion?

Yes, but naive recursion is inefficient; memoization or bottom-up dynamic programming avoids exponential runtime.

How do I handle single-character substrings?

Initialize dp[i][i] = 1 because each single character is a palindrome of length 1.

What if characters at the ends of a substring don't match?

Take the maximum of dp[i+1][j] and dp[i][j-1] to ensure the longest palindromic subsequence is preserved.

Can space complexity be optimized?

Yes, by using a rolling array along diagonals, space can be reduced from O(n^2) to O(n) while maintaining correctness.

#516

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。示例 1：输入： s = "bbbab" 输出： 4 解释：一个可能的最长回文子序列为 "bbbb" 。示例 2：输入： s = "…

字符串动态规划

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示字符串 $s$ 的第 $i$ 个字符到第 $j$ 个字符之间的最长回文子序列的长度。初始时 $f[i][i] = 1$ ，其余位置的值均为 $0$ 。

如果 $s[i] = s[j]$ ，那么 $f[i][j] = f[i + 1][j - 1] + 2$ ；否则 $f[i][j] = \max(f[i + 1][j], f[i][j - 1])$ 。

由于 $f[i][j]$ 的值与 $f[i + 1][j - 1]$ , $f[i + 1][j]$ , $f[i][j - 1]$ 有关，所以我们应该从大到小枚举 $i$ ，从小到大枚举 $j$ 。

答案即为 $f[0][n - 1]$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for i in range(n):
            f[i][i] = 1
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return f[0][-1]

speed

复杂度分析

指标	值
时间	complexity is O(n^2) due to iterating all substring ranges and updating the dp table. Space complexity is O(n^2) for the dp array, though it can be optimized to O(n) using a single rolling array along diagonals.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting use of dynamic programming rather than brute force recursion due to overlapping subproblems.
question_mark
Watch for correct handling of single-character substrings and matching endpoints.
question_mark
Check that candidates optimize state transitions and avoid unnecessary recomputation.

warning

常见陷阱

外企场景

error
Confusing subsequence with substring, which leads to incorrect dp updates.
error
Failing to correctly initialize dp for single-character substrings.
error
Overwriting dp values too early, which can break dependencies for longer substrings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual longest palindromic subsequence string, not just its length.
arrow_right_alt
Compute the minimum number of deletions to make the string a palindrome using the same dp logic.
arrow_right_alt
Handle strings with both uppercase and lowercase letters while maintaining the longest palindromic subsequence.

help

常见问题

外企场景

继续练习

#514 自由之路 #488 祖玛游戏 #474 一和零