516. 最长回文子序列

为保证权益，题目请参考 516. 最长回文子序列(From LeetCode).

解决方案1

Python

# 516. 最长回文子序列
# https://leetcode-cn.com/problems/longest-palindromic-subsequence/


class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0 for j in range(len(s))] for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1

        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])

        return dp[0][len(s) - 1]


if __name__ == "__main__":
    solution = Solution()
    print(solution.longestPalindromeSubseq("bbbab"))