一、题目描述
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:
输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:
"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。
提示：
1 <= s.length <= 1000
s 只包含小写英文字母
二、解题思路 & 代码
2.1 二维 dp
dp 数组的定义是：在子串 s [ i . . j ] s[i..j] s[i..j] 中，最长回文子序列的长度为 d p [ i ] [ j ] dp[i][j] dp[i][j]
两者情况：
if (s[i] == s[j])
// 它俩一定在最长回文子序列中
dp[i][j] = dp[i + 1][j - 1] + 2;
else
// s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
要求的就是 dp[0][n - 1]，也就是整个 s 的最长回文子序列的长度。
为了保证每次计算 d p [ i ] [ j ] dp[i][j] dp[i][j]，左下右方向的位置已经被计算出来，只能斜着遍历或者反着遍历：
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
# dp 数组全部初始化为 0
dp = [[0] * n for i in range(n)]
# base case
for i in range(n):
dp[i][i] = 1;
# 反着遍历保证正确的状态转移
for i in range(n-1, -1, -1):
for j in range(i+1, n):
# 状态转移方程
if (s[i] == s[j]):
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
# 整个 s 的最长回文子串长度
return dp[0][n - 1]
2.2 一维 dp
假设有一个二维数组 dp， d p [ i ] [ j ] dp[i][j] dp[i][j] 为 1 表示从位置 i 到位置 j 是否为回文字符串，那么当 s [ i − 1 ] = = s [ j + 1 ] s[i-1]==s[j+1] s[i−1]==s[j+1] 时，我们就能判断出， i − 1 i-1 i−1到 j + 1 j+1 j+1 是回文字字符串。然后在遍历过程中，你会发现，你只需要 j j j 位置的数据，不需要之前的，所以可以把二维变成两个一维数组。假如你在第二层循环从后往前遍历，还可以把两个一维数组合在一起。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [0] * n
for i in range(n):
dp[i] = 1
max_value = 0
for j in range(i-1, -1, -1):
tmp = dp[j]
if(s[j] == s[i]):
dp[j] = max_value + 2
max_value = max(tmp, max_value)
max_value = 0
for k in range(n):
max_value = max(max_value, dp[k])
return max_value
京公网安备 11010502036488号