中国空间站航天员首次出舱,大连市营商环境建设局网站,宿迁市房地产信息网,网站建设 设计创意一般来说#xff0c;子串和子数组都是连续的#xff0c;而子序列是可以不连续的#xff0c;遇到子序列问题基本上都是用动态规划求解。
53. 最大子数组和#xff08;剑指 Offer 42. 连续子数组的最大和#xff09;
class Solution:def maxSubArray(self, nums: List[int…一般来说子串和子数组都是连续的而子序列是可以不连续的遇到子序列问题基本上都是用动态规划求解。
53. 最大子数组和剑指 Offer 42. 连续子数组的最大和
class Solution:def maxSubArray(self, nums: List[int]) - int:n len(nums)dp [-10001] * (n1)dp[0] nums[0]for i in range(1, n):dp[i] max(dp[i-1] nums[i], nums[i])return max(dp)把 dp 数组定义为元素 dp[i] 表示以 nums[i] 为结尾的数组的连续子数组最大和。则初始条件为 dp[0] nums[0] 只有一个元素。如果知道了 dp[i-1]则 dp[i] 只有两种取值dp[i-1] nums[i] 和 nums[i]取两者中的较大值即可。
152. 乘积最大子数组
class Solution:def maxProduct(self, nums: List[int]) - int:n len(nums)if n 1:return nums[0]max_dp [0] * nmin_dp [0] * nmax_dp[0] min_dp[0] nums[0]for i in range(1, n):max_dp[i] max(max_dp[i-1] * nums[i], min_dp[i-1] * nums[i], nums[i])min_dp[i] min(max_dp[i-1] * nums[i], min_dp[i-1] * nums[i], nums[i])return max(max(max_dp), max(min_dp))求乘积的话能不能照搬上面的思路呢是不可以的因为乘积可能为负数每次只取较大值的话是不会选择负数的但是最大乘积可能由负负得正而来。解决方法是使用两个 dp 数组一个记录最大值一个记录最小值负的最大这样当第一次出现负数时结果会被 min_dp 记录下来而第二次出现负数的时候结果又会进入 max_dp。
674. 最长连续递增序列
class Solution:def findLengthOfLCIS(self, nums: List[int]) - int:n len(nums)dp [1] * nfor i in range(1, n):if nums[i-1] nums[i]:dp[i] dp[i-1] 1return max(dp)这题的关键词是连续所以如果在位置 i 的数字大于前一个数字就记录这个位置的序列长度dp[i]为前一个位置序列长度加一 dp[i-1] 1
300. 最长递增子序列
class Solution:def lengthOfLIS(self, nums: List[int]) - int:n len(nums)dp [1] * nfor i in range(n):for j in range(i):if nums[i] nums[j]:dp[i] max(dp[i], dp[j] 1)return max(dp)将 dp 数组定义为元素 dp[i] 表示以 nums[i] 为结尾的数组的最长递增子序列长度。初始化 dp 数组的每个元素都是1最小都是它本身长度为1。当遍历到 dp[i] 时它前面的每个 dp[j] j i 我们都是知道的需要从中找到能构成递增关系的nums[i] nums[j]最大长度 max(dp[i], dp[j] 1)。
1143. 最长公共子序列
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:m, n len(text1), len(text2)dp [[0 for _ in range(n1)] for _ in range(m1)]ans 0for i in range(1, m1):for j in range(1, n1):if text1[i-1] text2[j-1]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] max(dp[i-1][j], dp[i][j-1])return dp[-1][-1]dp[i][j]长度为 [0, i - 1] 的字符串 text1 与长度为 [0, j - 1] 的字符串 text2 的最长公共子序列
如果text1[i - 1] 与 text2[j - 1]相同那么找到了一个公共元素所以 dp[i][j] dp[i - 1][j - 1] 1; 如果 text1[i - 1] 与 text2[j - 1] 不相同那就看看 text1[0, i - 2] 与 text2[0, j - 1] 的最长公共子序列 和 text1[0, i - 1] 与 text2[0, j - 2] 的最长公共子序列取最大的。
如果 dp[i][j] 表示的是长度为 [0, i] 的字符串 text1 与长度为 [0, j] 的字符串 text2 的最长公共子序列在初始化上就麻烦不少代码如下
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:m, n len(text1), len(text2)dp [[0 for _ in range(n)] for _ in range(m)]ans 0if text1[0] text2[0]:dp[0][0] 1for i in range(1, m):if text1[i] text2[0] or dp[i-1][0] 1:dp[i][0] 1for j in range(1, n):if text1[0] text2[j] or dp[0][j-1] 1:dp[0][j] 1for i in range(1, m):for j in range(1, n):if text1[i] text2[j]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] max(dp[i-1][j], dp[i][j-1])return dp[-1][-1]673. 最长递增子序列的个数
class Solution:def findNumberOfLIS(self, nums: List[int]) - int:n len(nums)max_len ans 0dp [1] * ncnt [1] * nfor i in range(n):for j in range(i):# 如果当前元素可以加入递增序列使得dp[j]可以1if nums[i] nums[j]:# 遇到更长的递增子序列则更新if dp[j] 1 dp[i]:dp[i] dp[j] 1cnt[i] cnt[j] # 重置计数# 相同长度的递增子序列elif dp[j] 1 dp[i]:cnt[i] cnt[j]if dp[i] max_len:max_len dp[i]ans cnt[i] # 重置计数elif dp[i] max_len:ans cnt[i]return ans在上一题的基础上要对最长递增子序列的个数进行计数我们定义一个 cnt 数组cnt[i] 表示以 nums[i] 结尾的最长递增子序列的个数。设 nums 的最长递增子序列的长度为 maxLen那么答案 ans 为所有满足 dp[i] maxLen 的 i 所对应的 cnt[i] 之和。关键是对当前元素可以加入递增序列nums[i] nums[j]后的情况进行分类讨论以找出当前最长的递增子序列以及对它进行计数。
354. 俄罗斯套娃信封问题
class Solution:def maxEnvelopes(self, envelopes: List[List[int]]) - int:envelopes.sort(keylambda k: (k[0], -k[1]))n len(envelopes)dp [1] * nfor i in range(n):for j in range(i):if envelopes[i][1] envelopes[j][1]:dp[i] max(dp[i], dp[j] 1)return max(dp)关键思路是对宽度进行升序排序而对高度进行降序排序降序的目的是为了保证宽度相同时只有一个信封会被选入到最长递增子序列当中如果高度也是升序则会进入多个但是它们的宽度相同不符合题意。最后求关于高度的最长递增子序列的长度即为答案。
198. 打家劫舍
class Solution:def rob(self, nums: List[int]) - int:n len(nums)if n 2:return max(nums)dp [0] * ndp[0] nums[0]dp[1] max(nums[0], nums[1])for i in range(2, n):dp[i] max(dp[i-1], dp[i-2] nums[i])return dp[-1]这题可以看作是不相邻子序列的最大和dp[i] 表示到第 i 号房为止能偷到的最多钱状态转移方程为偷了第 i - 2 家后再偷第 i 家或者偷了第 i - 1 家不能偷第 i 家了两者的最大值。
740. 删除并获得点数
class Solution:def deleteAndEarn(self, nums: List[int]) - int:# 以数字作为下标对应点数作为值maxVal max(nums)total [0] * (maxVal 1)for val in nums:total[val] val# 打家劫舍问题n len(total)if n 1:return total[0]dp [0] * ndp[0] total[0]dp[1] max(total[0], total[1])for i in range(2, n):dp[i] max(dp[i-2] total[i], dp[i-1])return dp[n-1]将出现的数字作为下标数字出现次数 * 数字本身 数字对应的点数点数作为值构建一个 total 数组即变成了对于 total 数组的打家劫舍问题。
213. 打家劫舍 II
class Solution:def rob(self, nums: List[int]) - int:if not nums:return 0n len(nums)if n 1:return nums[0]if n 2:return max(nums)dp_1 [0] * ndp_2 [0] * ndp_1[0] nums[0]dp_1[1] max(nums[0], nums[1])dp_2[1] nums[1]dp_2[2] max(nums[1], nums[2])for i in range(2, n-1):dp_1[i] max(dp_1[i-2] nums[i], dp_1[i-1])for i in range(3, n):dp_2[i] max(dp_2[i-2] nums[i], dp_2[i-1])return max(dp_1[-2], dp_2[-1])房屋首尾相连了意味着偷了第一家就不能偷最后一家反之亦然。因此我们可以分类讨论把偷第一家和偷最后一家分别考虑用两个 dp 分别算出两个方案的结果取较大值即可。对于第一家和最后一家都不偷的情况其实已经被包含在上面两种情况里面了因为上面也只是考虑偷第一家或最后一家但不一定偷。
337. 打家劫舍 III
class Solution:def rob(self, root: TreeNode) - int:def postTravel(root):if not root: return 0, 0 # 偷不偷left postTravel(root.left)right postTravel(root.right)# 偷当前节点, 则左右子树都不能偷val_1 root.val left[1] right[1]# 不偷当前节点, 则取左右子树中最大的值val_2 max(left) max(right)return val_1, val_2return max(postTravel(root))这题实际上不算子序列问题而是树形 dp 问题但还是打家劫舍系列的所以放一起了。使用的是后序遍历因为要先获得左右子树的结果然后对于当前节点有偷或者不偷两种方案都需要返回取其中的较大值即可对于左右子树也是一样的。
