Leetcode 516. 最长回文子序列
题目描述
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入："bbbab" 输出：4 解释： 一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入："cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb"。
由题可知，回文序列不一定是连续子序列。
动态规划+二维数组
不妨以
f(i,j)
表示下标
i
到
j
的序列中最长回文序列长度，则只需要返回
f(0,len(s)-1)
即可。
根据回文串的特性：
- 若
![s[i]==s[j]](https://ask.qcloudimg.com/http-save/yehe-3177482/fn57ccth3l.svg)
s[i]==s[j]
，则有
f(i,j)= \begin{cases} f(i+1,j-1)+2, & \text {if j>i+1} \\ 2 ,& \text {if j=i+1} \end{cases}
- 若
![s[i]!=s[j]](https://ask.qcloudimg.com/http-save/yehe-3177482/1nrewa8lag.svg)
s[i]!=s[j]
，则有
![f(i,j)=max[f(i,j-1),f(i+1,j)]](https://ask.qcloudimg.com/http-save/yehe-3177482/idogmbqitj.svg)
f(i,j)=max[f(i,j-1),f(i+1,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]动态规划+一维数组
观察递推关系式可以发现，
f(i,j)
的值只与
f(i,j-1),f(i+1,j),f(i+1,j-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]本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读