经典题目
简述:找出整数数组中最长的严格递增子序列的长度;
# 子序列:由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。 输入:nums = [10, 9, 2, 5, 3, 7, 101, 18] 输出:4 解释:最长递增子序列为[2, 3, 7, 101],长度为4;[2, 3, 7, 18]也是,长度也为4 def lengthOfLIS(self, nums: List[int]) -> int: dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j]+1) return max(dp)
思路
利用动态规划五部曲的思路进行分析:
- dp[i]的定义:dp[i] 表示以 nums[i] 为结尾的最长上升子序列的长度
- 状态转移方程:当以 nums[i] 为结尾时,需要将 nums[i] 与之前所有元素进行对比来找到最长上升子序列,其时间复杂度为 。状态转移方程可以写做: ;
- dp[i] 的初始化:可以判断最长上升子序列的最小值为1;
- 确定遍历顺序:从前向后遍历即可;
- 举例推导dp数组,如下图:
需要通过一定的练习来帮助自己更快的确定dp以及状态转移方程。而举例推导dp数组是一个比较好的探索解题的方式
拓展题型
最长重复子数组
def findLength(self, nums1: List[int], nums2: List[int]) -> int: l1, l2 = len(nums1), len(nums2) dp = [[0] * (l2 + 1) for _ in range(l1 + 1)] # i/j == 0 时输出为 0 for i in range(1, l1 + 1): for j in range(1, l2 + 1): if nums1[i-1] == nums2[j-1]: # 判断是否相等 dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1) return max(max(row) for row in dp) # 遍历寻找最大值
最长公共子序列
def longestCommonSubsequence(self, text1: str, text2: str) -> int: l1, l2 = len(text1), len(text2) dp = [[0] * (l2+1) for _ in range(l1+1)] for i in range(1, l1+1): for j in range(1, l2+1): if text1[i-1] == text2[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]
不相交的线
# 和上述最长公共子序列代码相同 def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int: dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)] for i in range(1, len(nums1)+1): for j in range(1, len(nums2)+1): if nums1[i-1] == nums2[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]
不同的子序列
def numDistinct(self, s: str, t: str) -> int: dp = [[0]*len(s) for _ in range(len(t))] tmp=0 # 初始化数据 for i in range(len(s)): if t[0] == s[i]: tmp += 1 dp[0][i] = tmp # 遍历更新最大值 for i in range(1, len(t)): for j in range(i, len(s)): if t[i] == s[j]: dp[i][j] = dp[i-1][j-1] + dp[i][j-1] else: dp[i][j] = dp[i][j-1] return dp[-1][-1]
总结
此类题型多做点,核心在动态规划解法,尝试通过实例的图解来更好的推出转换公式:
- 当s[i]==s[j]时,dp[i][j]和dp[i-1][j-1]的关系(有时也和dp[i-1][j]有关,例如“不同子序列”题目)
- 当s[i] ≠ s[j]时,dp[i][j]和dp[i-1][j]、dp[i][j-1]的关系