516. Longest Palindromic Subsequence

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        
        # Can do a longest common subsequence of s and s[::-1]

        # memo = {}

        # def find(left, right):
        #     if left == right:
        #         return 1
        #     elif left + 1 == right:
        #         return 2 if s[left] == s[right] else 1
        #     elif (left, right) in memo:
        #         return memo[(left, right)]
        #     else:
        #         if s[left] == s[right]:
        #             longest = 2 + find(left + 1, right - 1)
        #         else:
        #             longest = max(find(left, right - 1), find(left + 1, right))

        #         memo[(left, right)] = longest

        #         return longest

        # return find(0, len(s) - 1)

        n = len(s)
        
        dp = [[0] * len(s) for _ in range(len(s))]

        for r in range(n, -1, -1):
            for l in range(r, n):
                if l == r:
                    dp[r][l] = 1
                elif l + 1 == r:
                    dp[r][l] = 2 if s[r] == s[l] else 1
                else:
                    if s[r] == s[l]:
                        dp[r][l] = 2 + dp[r + 1][l - 1]
                    else:
                        dp[r][l] = max(dp[r + 1][l], dp[r][l - 1])

        return dp[0][n - 1]