题目描述
思路解析
一句话答案：LeetCode 516 最长回文子序列：dp[i][j] 记 s[i..j] 的最长回文子序列长度，两端相等就取内部 +2、不等就丢一端取较大，按区间从短到长填表。时间 O(n²)、空间 O(n²)。
可跳字符的回文子序列，怎么算最长
给一个字符串 s，挑出一个正着读、倒着读都一样的子序列，要它尽可能长，返回长度。子序列可跳字符、但相对顺序不变，比如 bbbab 挑出 bbbb（跳过中间的 a）是长度 4 的回文。这题最容易和最长回文子串（LeetCode 5）弄混：子串要连续，子序列可跳着挑。
为什么不能把所有子序列列出来数
最直接是把所有子序列列出来逐个查，留最长的回文。可长度 n 的串有 2^n 个子序列，n 稍大就数不完（大 O 记号描述规模变大时操作数怎么涨，这里 O(2^n)）。它们大量重叠、同一小段被反复重验，把每段答案存下来只算一次就是动态规划（算过的子问题记下别重算）。
为什么状态要盯一个区间 dp[i][j]
回文判断天然从两头往中间收，状态就盯一个区间。定义 dp[i][j] 为子串 s[i..j] 的最长回文子序列长度，i 左端、j 右端，答案是 dp[0][n-1]。最短区间是单字符 dp[i][i]=1（一个字母自己就是回文），是长区间的基石；空区间（i 大于 j）记 0。
两端相等为什么 +2、不等为什么丢一端取大
算 dp[i][j] 只看两端 s[i] 和 s[j]。相等时它俩能当回文的最外层，把里面 s[i+1..j-1] 的最长回文包起来、两头各加一个，dp[i][j]=dp[i+1][j-1]+2。不等时它俩没法同时当两头，只能丢一个——丢左端剩 dp[i+1][j]，丢右端剩 dp[i][j-1]，取大：dp[i][j]=max(dp[i+1][j], dp[i][j-1])。
填表方向有坑：用到的 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1] 都比区间 [i,j] 更短。不能按行列顺序填，得按区间长度从短到长填——短的先算好、长的才有值可用。等价写法是外层 i 从大到小、内层 j 从小到大。
拿 bbbab 把这张表一格格填出来
下标 0 到 4 是 b、b、b、a、b。先铺对角线（表里从左上到右下、行号等于列号那条线），五个单字符 dp[i][i]=1。长度 2：dp[0][1] 相等，内部空记 0、+2 得 2；dp[1][2] 同理得 2；dp[2][3] 不等取 max(1,1)=1；dp[3][4] 不等取 1。
长度 3：dp[0][2] 相等得 dp[1][1]+2=3；dp[1][3] 不等取 max(dp[2][3]=1, dp[1][2]=2)=2；dp[2][4] 相等得 3。长度 4：dp[0][3] 不等取 max(2, 3)=3；dp[1][4] 相等得 dp[2][3]+2=3。长度 5：dp[0][4] 相等得 dp[1][3]+2=4，右上角就是答案 bbbb。
填表顺序填反、长度 2 漏 +2 会怎样
上三角约 n²/2 个格子、每格一次比较，时间 O(n²)；存整张二维表，空间 O(n²)，压成一维滚动数组（只留最近一行、循环覆盖旧值）可降到 O(n)。两个边界别弄错：填表顺序按行列填会读到还没算的长区间，必须按区间长度递增；长度 2 的区间相等时内部空记 0、+2 得 2，别漏这个 +2。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心就这一个表：行是左端 i、列是右端 j。我们按「区间从短到长」填，短区间先算好，长区间才有依赖可用。
先铺对角线：每个单字符 'b' 自己就是一个回文，dp[0][0] = 1。这是最短区间，作为后面长区间的基石。
先铺对角线：每个单字符 'b' 自己就是一个回文，dp[1][1] = 1。这是最短区间，作为后面长区间的基石。
先铺对角线：每个单字符 'b' 自己就是一个回文，dp[2][2] = 1。这是最短区间，作为后面长区间的基石。
先铺对角线：每个单字符 'a' 自己就是一个回文，dp[3][3] = 1。这是最短区间，作为后面长区间的基石。
先铺对角线：每个单字符 'b' 自己就是一个回文，dp[4][4] = 1。这是最短区间，作为后面长区间的基石。
两端 'b' 和 'b' 相等：把它俩套在外面，里面 s[1..0] 的最长回文（0）直接 +2。两端一对相等字符，能让回文加长 2。
落子：dp[0][1] = 2。区间 s[0..1]（"bb"）的最长回文子序列长度。
两端 'b' 和 'b' 相等：把它俩套在外面，里面 s[2..1] 的最长回文（0）直接 +2。两端一对相等字符，能让回文加长 2。
落子：dp[1][2] = 2。区间 s[1..2]（"bb"）的最长回文子序列长度。
两端 'b' 和 'a' 不相等：这俩没法同时当回文的两头，只能丢一个——丢左端看 dp[3][3]=1，丢右端看 dp[2][2]=1，取大的。
落子：dp[2][3] = 1（取了较大的那条路）。
两端 'a' 和 'b' 不相等：这俩没法同时当回文的两头，只能丢一个——丢左端看 dp[4][4]=1，丢右端看 dp[3][3]=1，取大的。
落子：dp[3][4] = 1（取了较大的那条路）。
两端 'b' 和 'b' 相等：把它俩套在外面，里面 s[1..1] 的最长回文（1）直接 +2。两端一对相等字符，能让回文加长 2。
落子：dp[0][2] = 3。区间 s[0..2]（"bbb"）的最长回文子序列长度。
两端 'b' 和 'a' 不相等：这俩没法同时当回文的两头，只能丢一个——丢左端看 dp[2][3]=1，丢右端看 dp[1][2]=2，取大的。
落子：dp[1][3] = 2（取了较大的那条路）。
两端 'b' 和 'b' 相等：把它俩套在外面，里面 s[3..3] 的最长回文（1）直接 +2。两端一对相等字符，能让回文加长 2。
落子：dp[2][4] = 3。区间 s[2..4]（"bab"）的最长回文子序列长度。
两端 'b' 和 'a' 不相等：这俩没法同时当回文的两头，只能丢一个——丢左端看 dp[1][3]=2，丢右端看 dp[0][2]=3，取大的。
落子：dp[0][3] = 3（取了较大的那条路）。
两端 'b' 和 'b' 相等：把它俩套在外面，里面 s[2..3] 的最长回文（1）直接 +2。两端一对相等字符，能让回文加长 2。
落子：dp[1][4] = 3。区间 s[1..4]（"bbab"）的最长回文子序列长度。
两端 'b' 和 'b' 相等：把它俩套在外面，里面 s[1..3] 的最长回文（2）直接 +2。两端一对相等字符，能让回文加长 2。
落子：dp[0][4] = 4。区间 s[0..4]（"bbbab"）的最长回文子序列长度。
右上角 dp[0][4] = 4，就是整个串 "bbbab" 的最长回文子序列长度（即 "bbbb"，跳过中间的 a）。
边界先想清。
两个高频追问。
参考代码
def longestPalindromeSubseq(s): n = len(s) dp = [[0]*n for _ in range(n)] for i in range(n): dp[i][i] = 1 for L in range(2, n+1): for i in range(0, n-L+1): j = i + L - 1 if s[i] == s[j]: dp[i][j] = (dp[i+1][j-1] if i+1<=j-1 else 0) + 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) return dp[0][n-1]复杂度
- 时间：O(n²)，上三角约 n²/2 格，每格 O(1)
- 空间：O(n²)，整张二维表
易错点
面试追问把动画讲成自己的话
追问为什么要按区间长度从小到大填？
追问能优化空间吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
优美的排列
LeetCode 526 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题