专业做网站的公司有没有服务器,公司建立网站的必要性,云南旅行社网站设计,山东宏远建设有限公司网站Day52 动态规划part13
300.最长递增子序列
leetcode链接#xff1a;300. 最长递增子序列 - 力扣#xff08;LeetCode#xff09;
题意#xff1a;给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列#xff0c;删除300. 最长递增子序列 - 力扣LeetCode
题意给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1
输入nums [10,9,2,5,3,7,101,18]输出4解释最长递增子序列是 [2,3,7,101]因此长度为 4 。
思路
dp数组定义dp[i]是以nums[i]为结尾的最长递增子序列长度状态转移方程位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值。所以if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);dp[i]的初始化每一个i对应的dp[i]即最长递增子序列起始大小至少都是1遍历顺序两层循环。dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来那么遍历i一定是从前向后遍历。推导扩展也可以用贪心做
class Solution:def lengthOfLIS(self, nums: List[int]) - int:dp [1] * len(nums)for i in range(1, len(nums)):for j in range(0, i):if nums[j] nums[i]: dp[i] max(dp[i], dp[j]1)print(dp)return max(dp)674. 最长连续递增序列
leetcode链接. - 力扣LeetCode
题意相比于上一题这题是连续的
思路只用和i-1比较了都不用有循环了
class Solution:def findLengthOfLCIS(self, nums: List[int]) - int:dp [1]*len(nums)for i in range(1, len(nums)):if nums[i-1] nums[i]:dp[i] max(dp[i], dp[i-1]1)return max(dp)718. 最长重复子数组
leetcode链接718. 最长重复子数组 - 力扣LeetCode
题意给两个整数数组 A 和 B 返回两个数组中公共的、长度最长的子数组的长度。
示例
输入
A: [1,2,3,2,1]B: [3,2,1,4,7]输出3解释长度最长的公共子数组是 [3, 2, 1] 。
思路用二维数组可以记录两个字符串的所有比较情况
确定dp数组dp table以及下标的含义dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]。 特别注意 “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 递推公式dp[i][j] dp[i-1][j-1]1初始化根据dp[i][j]的定义dp[i][0] 和dp[0][j]其实都是没有意义的但dp[i][0] 和dp[0][j]要初始值因为 为了方便递归公式dp[i][j] dp[i - 1][j - 1] 1;所以dp[i][0] 和dp[0][j]初始化为0。举个例子A[0]如果和B[0]相同的话dp[1][1] dp[0][0] 1只有dp[0][0]初始为0正好符合递推公式逐步累加起来。遍历顺序外层for循环遍历A内层for循环遍历B。其实先遍历B也可以的
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:lena len(nums1)lenb len(nums2)dp [[0]*(lenb1) for i in range(lena1)] #注意b是行a是列result 0for i in range(1, lena1):for j in range(1, lenb1):# print(i,j,nums1[i-1],nums2[j-1])if nums1[i-1] nums2[j-1]:dp[i][j] dp[i-1][j-1] 1if dp[i][j]result:result dp[i][j]# result max(result, max(dp[i]))# print(dp)return result
