516. 最长回文子序列

https://leetcode-cn.com/problems/longest-palindromic-subsequence/submissions/

解法一：dp

用dp[i][j]表示s[i...j]的最长回文子序列 当s[i] == s[j]时，s[i...j]的最长回文子序列由s[i+1...j-1]与头尾的s[i]和s[j]构成，即dp[i][j] = dp[i+1][j-1]+2 当s[i] != s[j]时，s[i...j]的最长回文子序列就是s[i+1...j]和s[i...j-1]中较长的，即dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 边界：串长度为1，即i==j时，dp[i][j]=1；i<j时，dp[i][j]=0，因此只需要遍历上三角矩阵

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        if n == 1:
            return n
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if i == j:	#对角线
                    dp[i][j] = 1
                    continue
                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][n-1]