题目描述
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入："bbbab"
输出：4
解释： 一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入："cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb"。
由题可知，回文序列不一定是连续子序列。
动态规划+二维数组
不妨以 表示下标
到
的序列中最长回文序列长度，则只需要返回
即可。
根据回文串的特性：
若
，则有
若
，则有
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp=[[0]*len(s) for i in range(len(s))]
for j in range(len(s)):
dp[j][j]=1
for i in range(j-1,-1,-1):
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])
return dp[0][len(s)-1]
动态规划+一维数组
观察递推关系式可以发现， 的值只与
有关，在二维数组中体现为每个元素的值，由下方、右方和右下方三个元素确定。由此可优化递推顺序为：由下向上，由右向左的方式递推，因此可优化二维存储空间为一维空间。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp=[1]*len(s)
for j in range(len(s)):
tmp=1
for i in range(j-1,-1,-1):
if s[i]==s[j]:
tmp,dp[i+1]=2 if j==i+1 else dp[i+1]+2,tmp
else:
tmp,dp[i+1]=max(tmp,dp[i]),tmp
dp[0]=tmp
return dp[0]
