LeetCode 516. 最长回文子序列

题目

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

例：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

方法：动态规划

• dp[i][j] 表示下标为 [i, j] 组成的字符串存在的最长的回文子序列的长度

• 初始化 dp[i][i]，即对角线部分，因为无法通过之后的计算得到。dp[i][i] 表示下标为 [i, i] 组成的字符串存在的最长的回文子序列的长度，即以 i 为下标的单个字符，所以设置长度为 1

• 外部循环为从下到上的循环，内部循环为从左到右的循环

  • 若字符串的首尾字符相同，那么此时字符串的最长回文子序列的长度为下标为 [i+1, j-1] 组成的字符串存在的最长的回文子序列的长度加二，即 dp[i+1][j-1] + 2
  • 若字符串的首尾字符不同，那么此时字符串的最长回文子序列的长度有两个选择：s[i] 被加入回文串而 s[j] 不被加入回文串，那么此时组成字符串的下标为 [i, j-1]，所以长度为 dp[i][j-1]；s[j] 被加入回文串而 s[i] 不被加入回文串，那么此时组成字符串的下标为 [i+1, j]，所以长度为 dp[i+1][j]
    ※ 因为求的时最长回文序列的长度，所以取较大值

• 返回长度，因为内外部的遍历顺序，所以最大值是位于右上角的

class Solution(object):
    def longestPalindromeSubseq(self, s):
        dp = [[0] * len(s) for row 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][-1]

参考

代码相关：https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html