lc516.最长回文子序列

题目链接

这是一个区间dp的题目。我们先定义一个二维数组dp, dp[i][j]表示字符串s[i…j]的最长回文子序列的长度。假设对某个序列上的两个位置i，j，有另外的两个位置i+1和j-1。假设我们已经知道了dp[i+1][j-1]，我们如何计算dp[i][j]呢？我们只需要观察s[i]等不等于s[j]，当s[i]==s[j]时，那么就说明在原先的基础上又增加了回文子序列的长度，dp[i][j] = dp[i+1][j-1]+2，当s[i]!=s[j]时，那么说明s[j], s[j]中至少有一个不在回文子序列中，这时dp[i][j]只需取两者之间的最大值即可。即dp[i][j] = max(dp[i][j-1], dp[i+1][j])。由于每一个字符自身能构成一个回文子序列且长度为1，所以dp[i][j]为1。我们只考虑i小于j的情况，因为如果考虑i大于j会重复。所以我们可以将dp二维表的下半三角设置成0。至此我们得到了一个斜对角线为1，下半三角都为0的二维矩阵。为了填充剩余的上半三角，我们需要斜向遍历，或从下向上，从左往右依次计算。最后返回的结果是第一行的最后一个元素。

这个算法的时间复杂度是O（N^2），空间复杂度是O（N^2）。

python:

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        size = len(s)
        dp = [[0]*size for _ in range(size)]

        for i in range(size):
            dp[i][i] = 1
        
        for x in range(size-2, -1, -1):
            for y in range(x+1, size):
                if s[x] == s[y]:
                    dp[x][y] = dp[x+1][y-1] + 2
                else:
                    dp[x][y] = max(dp[x+1][y], dp[x][y-1])
        return dp[0][-1]