前言

继续总结动态规划 本篇是子序列问题

1、子序列问题模板

子序列是不连续的 较子串和子数组更困难 通常是求一个怎么怎么样的最长子序列 时间复杂度⼀般都是 O(n^2)

模板一

一个一维dp数组

dp = [1] * n for i in range(1, n): for j in range(i): dp[i] = max(dp[i], dp[j]+...)

比如第一篇里的最长上升子序列（下面会再次写一下）

模板二

一个二维dp数组

dp = [[1] * n for _ in range(n)] for i in range(1, n): for j in range(i): if arr(i)==arr(j): dp[i][j] = dp[i][j] + ... else: dp[i][j] = max(...)

主要是涉及两个字符串的情况 有两个状态

2、最长上升子序列

leet上300题最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。 例子 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

注意子序列不连续

分析：

状态：最长上升子序列的长度dp：前n个数中最长上升子序列的长度状态转移方程：dp[i] = max(dp[i], dp[j] + 1)， j < i

于是我们可以写出解

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) dp = [1] * n for i in range(1, n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1) return max(dp or [0])

3、最长回文子序列

leet上516题

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。 可以假设 s 的最大长度为 1000

分析：

dp含义：在⼦串 s[i…j] 中，最⻓回⽂⼦序列的⻓度为 dp[i][j]状态转移：如果s[j] == s[i]，则都可以加上去，即dp[i][j] = 2 + dp[i + 1][j - 1]；不然就说明不能同时出现在最长回文子序列里，分别加入，看哪个更长dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = 1 for j in range(i - 1, -1, -1): if s[j] == s[i]: dp[j][i] = 2 + dp[j + 1][i - 1] else: dp[j][i] = max(dp[j + 1][i], dp[j][i - 1]) return dp[0][n - 1]

4、最长公共子序列

leet上1143题

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。 若这两个字符串没有公共子序列，则返回 0。

分析：

dp的含义：对于 s1[1…i] 和 s2[1…j] ，它们的 LCS ⻓度是 dp[i][j]状态转移：若A[i - 1] == B[j - 1]，说明这个字符在最长公共子序列里，dp[i][j] = dp[i - 1][j - 1] + 1；否则至少有一个不在，那比个大小就是了dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) class Solution: def longestCommonSubsequence(self, A: str, B: str) -> int: m, n = len(A), len(B) res = 0 dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if A[i - 1] == B[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[-1][-1]

结语

掌握模板 分析dp 也就这么一回事儿了