題目描述
給定一個(gè)字符串s渊涝，找到其中最長(zhǎng)的回文子序列囤锉≌奢海可以假設(shè)s的最大長(zhǎng)度為1000屯耸。
示例 1:
輸入："bbbab"
輸出：4
解釋： 一個(gè)可能的最長(zhǎng)回文子序列為 "bbbb"拐迁。
示例 2:
輸入："cbbd"
輸出：2
解釋：一個(gè)可能的最長(zhǎng)回文子序列為 "bb"。
由題可知疗绣，回文序列不一定是連續(xù)子序列线召。
動(dòng)態(tài)規(guī)劃+二維數(shù)組
不妨以 表示下標(biāo)
到
的序列中最長(zhǎng)回文序列長(zhǎng)度，則只需要返回
即可多矮。
根據(jù)回文串的特性：
若
缓淹，則有
若
，則有
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]
動(dòng)態(tài)規(guī)劃+一維數(shù)組
觀察遞推關(guān)系式可以發(fā)現(xiàn)塔逃， 的值只與
有關(guān)讯壶，在二維數(shù)組中體現(xiàn)為每個(gè)元素的值，由下方湾盗、右方和右下方三個(gè)元素確定伏蚊。由此可優(yōu)化遞推順序?yàn)椋河上孪蛏希捎蚁蜃蟮姆绞竭f推格粪，因此可優(yōu)化二維存儲(chǔ)空間為一維空間躏吊。
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]
