越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/longest-palindromic-subsequence/

This is a 2D dynamic programming problem. We let dp[i][j] be the length of the longest palindromic subsequence (LPS) in s[i..j]. Obviously we have dp[i][i] = 1. Specially we define dp[i][i-1] = 0.

Then we can write the occurrences. If s[i] = s[j], the LPS in s[i..j] is just the LPS in s[i+1..j-1] surrounded by s[i] and s[j]. Therefore, dp[i][j] = dp[i+1][j-1] + 2. If s[i] != s[j], we can only depend on the values we have already calculated: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

In the 2D array dp, an element might depend on the elements above it, to its right, or to its upper right. Therefore, we can fill out the array diagonally. This approach has time and space complexity equal to the size of the dp array, which is $O(n^2)$. But since any element only depends on elements near it, we can get rid of the elements that are no longer useful and reduce the space complexity to $O(n)$ (code not shown).

这是一道二维动态规划的题目。我们令 dp[i][j] 表示 s[i..j] 中最长回文子序列的长度。显然,dp[i][i] = 1,特别地定义 dp[i][i-1] = 0

然后我们可以写出状态转移方程。当 s[i] = s[j] 时,s[i..j] 中最长回文子序列即是 s[i+1..j-1] 中最长回文子序列两端加上 s[i]s[j]。因此,dp[i][j] = dp[i+1][j-1] + 2。而 s[i] != s[j] 时,我们只能依赖之前计算好的数值:dp[i][j] = max(dp[i+1][j], dp[i][j-1])

在二维数组 dp 中,每个元素可能依赖它上方、右方、右上方三个元素,因此我们可以按对角线填满 dp。这样的方法的时间复杂度与空间复杂度都与 dp 的大小相同,即 $O(n^2)$。而由于每个元素只依赖附近的元素,每次循环中我们可以舍弃已经不会再用到的元素,因此空间复杂度可以减少到 $O(n)$,在这里不附代码。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for w in range(2, n + 1): # window size
            for i in range(n - w + 1):
                j = i + w - 1
                if s[i] == s[j]:
                    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][len(s) - 1]