Longest Palindromic Subsequence LeetCode solution in Python

1
class Solution:
2
    def longestPalindromeSubseq(self, s: str) -> int:
3
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
4
        for k in range(1, len(s) + 1):
5
            for i in range(len(s) - k + 1):
6
                j = k + i - 1
7
                if i == j:
8
                    dp[i][j] = 1
9
                elif i + 1 == j and s[i] == s[j]:
10
                    dp[i][j] = 2
11
                elif s[i] == s[j]:
12
                    dp[i][j] = dp[i + 1][j - 1] + 2
13
                else:
14
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
15
        return dp[0][-1]