leetcode-516-最长回文子序列

发表于 更新于 阅读次数： 本文字数： 548 阅读时长 ≈ 1 分钟
简介：leetcode-516-最长回文子序列

题目

https://leetcode.cn/problems/longest-palindromic-subsequence/description/?envType=study-plan-v2&envId=dynamic-programming

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        m,n = len(s),len(s) 
        lst = [[0 for j in range(n)] for i in range(m)]

        for i in range(m):
            lst[i][i] = 1
        # print(lst)

        for i in range(m-2,-1,-1):
            for j in range(i+1,n):
                if s[i] == s[j]:
                    lst[i][j] = lst[i+1][j-1] + 2
                else:
                    lst[i][j] = max(lst[i+1][j], lst[i][j-1])
        # print(lst)

        return lst[0][m-1]

思路

https://www.bilibili.com/video/BV15g4y1E7n4/?vd_source=18c316629aa624cb452f9acf73595c09