DP-LeetCode516. 最长回文子序列（Python）
1、题目描述
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
类似题升级版本，子序列可以跳字符
相关题： LeetCode5. 最长回文子串（双指针、中心扩展算法）
https://blog.csdn.net/IOT_victor/article/details/105961369
class Solution(object):
def longestPalindromeSubseq(self, s):
n = len(s)
dp = [[0] * n for _ in range(n)] # dp 数组全部初始化为 0
# base case, 对角线必为1，i < j为0
for i in range(n):
dp[i][i] = 1
# 从下往上遍历
# 反着遍历保证正确的状态转移
for i in range(n - 1, -1, -1):
for j in range(i + 1, n, 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])
# 整个 s 的最长回文子串长度
return dp[0][n - 1]
S = Solution()
s = "bbbab"
print(S.longestPalindromeSubseq(s))
参考
题解：labuladong
https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/
视频：九章算法
NLP_victor
原创文章 188获赞 229访问量 6万+
关注
私信
展开阅读全文
作者：NLP_victor
