打卡记录

最长回文子序列（区间DP）

链接

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        max = lambda x, y: x if x > y else y
        for i in range(n - 1, -1, -1):
            f[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]: f[i][j] = f[i + 1][j - 1] + 2
                else: f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return f[0][-1]