题目重点：把子序列和子串分清，推导两端相等/不等的区间递推、填表方向及 O(n²) 复杂度。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练输入为字符串，允许删除任意字符但保留剩余字符原相对顺序，返回最长回文子序列长度。
- 空串返回 0；字符按代码点精确比较，若需 Unicode 规范化须另定义。
- 不把‘子序列’误作连续的‘子串’；若原面试只要求输出一条序列，需增加回溯。
解题路线
- 设 dp[l][r] 是闭区间 text[l:r+1] 的最长回文子序列长度，单字符为 1、空区间为 0。
- 若两端字符相同，可取两端加内部最优：2+dp[l+1][r−1]；若不同，最优必排除至少一端，取 max(dp[l+1][r],dp[l][r−1])。
- 按 l 从右到左、r 从 l+1 到右填表，确保依赖的短区间已算。答案 dp[0][n−1]。可做 O(n) 空间压缩，但需要保存旧的左下对角值以免覆盖。
- 若时间只够非最优解，也可枚举所有 2^n 子序列并逐一验回文；这是正确但指数级的基线，面试官允许不最优不表示应把它当最终推荐方案。
手动走一遍
text='bbbab'：取下标 0、1、2、4 可得 'bbbb'，长度 4；它不是连续子串。'cbbd' 则可取 'bb' 长 2；相邻区间递推最终会得到这两个结果。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Length of the longest palindromic subsequence, not substring."""
def longest_palindromic_subsequence(text: str) -> int:
n = len(text)
if n == 0:
return 0
dp = [[0] * n for _ in range(n)]
for left in range(n - 1, -1, -1):
dp[left][left] = 1
for right in range(left + 1, n):
if text[left] == text[right]:
dp[left][right] = 2 + (dp[left + 1][right - 1] if right - left > 1 else 0)
else:
dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
return dp[0][-1]
复杂度
n 个字符有 O(n²) 个区间，每格 O(1)，时间 O(n²)、表空间 O(n²)；若只求长度可压到 O(n) 空间。暴力基线 O(n·2^n)。
易错点与追问
容易失分的边界
- 把最长回文子串的中心扩展用于子序列，漏掉不连续答案。
- 两端相等时忘记长度 2 区间的内部空区间。
- 错误填表顺序读到尚未计算的 dp。
- 题目未说明返回长度或序列，却宣称输出格式确定。
继续深挖
- 如何回溯一条最长序列，并确定同长度时的选择？
- 只用 O(n) 空间时依赖旧对角值如何保存？
- 若要求最少删除使字符串回文，答案与 LPS 有何关系？
