516. 最长回文子序列

题目链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence/
难度：中等

描述：
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

题解

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        # r[i][j]代表s[i:j+1]的最长回文序列长度
        r = [[0]*n for _ in range(n)]
        for i in range(n-1, -1, -1):
            r[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    r[i][j] = r[i+1][j-1] + 2
                else:
                    r[i][j] = max(r[i+1][j], r[i][j-1])
        return r[0][-1]