题目重点：返回可跳过字符的最长回文长度，解释相等两端递推和滚动数组依赖。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 返回长度，子序列可不连续、顺序不变；大小写敏感，空串返回0。不是最长回文子串。
解题路线
- dp[l][r]表示区间内最长回文子序列。l=r为1；text[l]=text[r]时两端可同时选，得到2+dp[l+1][r-1]；不等时至少一个端点不选，取max(dp[l+1][r],dp[l][r-1])。
- 相等两端为何可选？如果某最优仅用了一个端点，可用另一个相同字符替换其匹配端，或添加匹配两端构造不更差结果；标准区间最优性支持该递推，不需把substring当成subsequence。
- left从右向左，right从left+1向右，一行dp[right]更新前是dp[left+1][right]，dp[right-1]已是dp[left][right-1]，diagonal保留dp[left+1][right-1]。每轮先保存old再覆盖。
- 只算长度可以O(n)空间；恢复具体字符序列需保留选择信息或额外重算。不要把一行dp中的不同right值拼接成结果，它们对应不同区间最优。
手动走一遍
bbbab最长子序列bbbb长度4，最长连续回文只有bbb长度3。cbbd可选bb长度2；abc长度1；空串0，单字符1。滚动DP中相邻相等两端用空内区间0，所以结果2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def longest_palindrome_subsequence(text):
"""Length, not substring; rolling interval DP."""
n=len(text)
if n==0:return 0
dp=[1]*n
for left in range(n-2,-1,-1):
diagonal=0
for right in range(left+1,n):
old=dp[right]
dp[right]=2+diagonal if text[left]==text[right] else max(dp[right],dp[right-1])
diagonal=old
return dp[-1]
复杂度
时间O(n²)、辅助空间O(n)，输出长度O(1)。二维表O(n²)空间支持直接重构。若用lcs(text,reverse(text))只求长度可等价，但任意LCS重构并不能未经验证就宣称给出了所需回文。
易错点与追问
容易失分的边界
- 把区间内所有字符都要求连续，得到的是另一个问题。
- diagonal没有先保存旧dp[right]会污染依赖。
继续深挖
- 最少删除成回文为何等于n−LPS长度？任何保留回文都是子序列，最大保留即可最少删除。
- 多个最优解时字典序最小回文，需要什么额外比较成本？
