LeetCode 516 Longest Palindromic Subsequence

LeetCode

Given a string s, find the longest palindromic subsequence‘s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.

Example 2:

Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.

Constraints:

1 <= s.length <= 1000 s consists only of lowercase English letters.

题目大意：

求字符串中最长回文序列

算法思路：

一开始看到子序列如LIS就想用DP，dp[i]表示以s[i]为结尾的最长回文子序列。但不容易推导公式，难点是没有限制左边界
所以应该扩展到二维dp[i][j]表示[i, j]之间的最长回文子序列。公式就简单多了

dp[i][j] = dp[i+1][j-1] + 2,             s[i] == s[j]
         = max(dp[i+1][j], dp[i][j-1]),  s[i] != s[j]

注意事项：

1. 难点是想到用二维DP(区间型DP)。用区间型递归模板，注意dp[i + 1][j]并不是i - 1
2. 初始值为dp[i][i] = 1

Python代码：

def longestPalindromeSubseq(self, s: str) -> int:
	dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
	for i in range(len(s)):
		dp[i][i] = 1
	for k in range(1, len(s)):
		for i in range(len(s) - k):
			j = i + k
			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][-1]

算法分析：

时间复杂度为O(n*n)，空间复杂度O(n*n)