难度: Medium
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
Submission
运行时间: 1192 ms
内存: 221.4 MB
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
memo = dict()
l = len(s)
def dp(i, j):
if i == j:
return 1
if i > j:
return 0
if (i, j) in memo:
return memo[(i, j)]
if s[i] == s[j]:
memo[(i, j)] = dp(i+1, j-1) + 2
else:
memo[(i, j)] = max(dp(i+1, j), dp(i, j-1))
return memo[(i, j)]
return dp(0, l-1)
Explain
这个题解采用动态规划的思路来解决最长回文子序列问题。使用一个二维的备忘录memo来存储子问题的结果，避免重复计算。dp(i, j)表示字符串s在区间[i, j]内的最长回文子序列的长度。如果s[i]和s[j]相等，那么dp(i, j) = dp(i+1, j-1) + 2，否则dp(i, j) = max(dp(i+1, j), dp(i, j-1))。最终返回dp(0, len(s)-1)即为整个字符串s的最长回文子序列长度。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
memo = dict()
l = len(s)
def dp(i, j):
if i == j:
return 1
if i > j:
return 0
if (i, j) in memo:
return memo[(i, j)]
# s[i]和s[j]相等，公共子序列长度加2
if s[i] == s[j]:
memo[(i, j)] = dp(i+1, j-1) + 2
# 否则取dp(i+1, j)和dp(i, j-1)的最大值
else:
memo[(i, j)] = max(dp(i+1, j), dp(i, j-1))
return memo[(i, j)]
# 返回s[0, l-1]的最长回文子序列长度
return dp(0, l-1)
Explore
在解决最长回文子序列问题时，使用二维备忘录memo是因为状态dp(i, j)依赖于它的子状态dp(i+1, j-1)，dp(i+1, j)和dp(i, j-1)，这些状态在不同的i和j组合下具有不同的值。一维数组无法同时保存对应于不同子序列范围的多个状态值，因此需要二维数组来存储状态，其中每一个元素dp[i][j]表示子序列s[i...j]的最长回文子序列长度。
在字符串中，如果索引i大于索引j，意味着子序列的起始位置在终止位置之后，这种情况下，子序列是不可能存在的，因此其长度为0。这是根据字符串子序列定义和问题约束得出的逻辑结论，有效避免了无效或错误的子序列长度计算。
在边界条件dp(i, i)中返回1是基于单个字符总是回文的考虑。即在字符串s中，任何单独的字符s[i]构成的子序列自身就是一个长度为1的回文子序列。因此，对于任何i，dp(i, i)的值应为1，表示单字符子序列的最长回文子序列长度。
递推公式dp(i, j) = dp(i+1, j-1) + 2用于处理s[i]与s[j]相等的情况。在这种情况下，s[i]和s[j]可以作为当前考虑的子序列的两端，它们自身构成回文的一部分。因此，除了这两个字符外，子序列s[i+1...j-1]的最长回文子序列长度（由dp(i+1, j-1)给出）需要加上这两个匹配字符，因此总长度增加2。这个递推关系说明了如何从已知的子问题构建出更大问题的解。