最长回文子序列-动态规划516-python

没看答案。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        '''
        state: dp[i][j]表示s[i:j]中的最长回文子序列
        basecase: 先遍历列（从下到上），再遍历行（从左到右）
        transfer: i==j，dp[i][j]=1；
                  i==j-1，若s[i]==s[j]，则dp[i][j]=2，
                          若s[i]!=s[j]，则dp[i][j]=1。
                  若j-i>1，若s[i]==s[j]，则dp[i][j]考虑保留s[i]和s[j]和只保留s[i]或s[j]三种情况；
                           若s[i]!=s[j]，则dp[i][j]也考虑以上三种情况；                  
        result: dp[0][-1]
        '''

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

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

        return dp[0][-1]