[leetcode]516_最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成

解题思路：【动态规划】

dp[i][j]：表示区间范围[i,j]的最长回文序列数；初始化为0

    当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况
    情况一：下标i 与 j相同，同一个字符例如a，dp[i][j] = 1
    情况二：下标i 与 j相差为1，例如aa, dp[i][j] = 2
            或者 dp[i][j] = dp[i + 1][j - 1] + 2;
            数组所有初始化为0，相差1时，dp[i + 1][j - 1] = 0
    情况三：下标：i 与 j相差大于1的时候，
        例如cabac，此时s[i]与s[j]已经相同了，
        我们看i到j区间最长回文序列数取决于aba中的回文序列数，
        那么aba的区间就是 i+1 与 j-1区间，即dp[i][j] = dp[i + 1][j - 1] + 2
 

可参考博文：[leetcode]647_回文子串-CSDN博客

class Solution:
    """
    dp[i][j]: 从i 到 j的最长回文子序列数
    """
    def max_palindrome_list_dp(self,s):
        length = len(s)
        dp = [[0]*length for _ in range(length)]
        for i in range(length - 1, -1, -1):
            for j in range(i, length):
                if s[i] == s[j]:
                    if i - j == 0:
                        dp[i][j] = 1
                    else:
                        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][-1]

if __name__ == '__main__':
    s = input()
    result_s = Solution().max_palindrome_list_dp(s)
    print(result_s)

仅作为代码记录，方便自学自查自纠