leetcode 第六天 动态规划（子序列问题）python
创始人
2025-06-01 14:41:05
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
300 最长递增子序列
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:#dp[i]表示第i个节点目前最长递归子序列长度#如果nums[i] >nums[j]#dp[i]=(dp[i],dp[j]+1)dp=[1]*len(nums)res=0for i in range(0,len(nums)):for j in range(0,i):if nums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)if dp[i]>res:res=dp[i]return res
674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:#dp[i]表示第i个节点前的最长连续递增子序列dp=[1]*len(nums)for i in range(len(nums)-1):if nums[i]718. 最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:#dp[i][j]表示 节点nums1 中i之前与nums2 j之前最长的公共子数组长度#递推公式： if nums2[i-1] ==nums1[j-1]:# dp[i][j]=dp[i-1][j-1]+1dp=[[0]*(len(nums1)+1) for _ in range(len(nums2)+1)]res=0for i in range(1,len(nums2)+1):for j in range(1,len(nums1)+1):if nums2[i-1] ==nums1[j-1]:dp[i][j]=dp[i-1][j-1]+1if dp[i][j]>res:res=dp[i][j]return res
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:#dp[i][j] 表示节点i ，j之前公共子序列的最长长度# if text1[i]=text2[j]；#dp[i][j]=dp[i-1][j-1]+1#else dp[i][j]=max(dp[i-1][j]+dp[i][j-1])dp=[[0]*(len(text2)+1) for _ in range (len(text1)+1)]for i in range(1,len(text1)+1):for j in range(1,len(text2)+1):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]
相关内容
热门资讯
重大通报“丫丫诗词有挂么”(原...
您好：丫丫诗词这款游戏可以开挂，确实是有挂的，需要软件加微信【6262387】，很多玩家在乐酷副厅这...
开心联盟.是不是有挂［必胜开挂...
开心联盟.是不是有挂［必胜开挂神器］亲，开心联盟这个游戏其实有挂的，确实是有挂的，需要了解加客服微信...
［实测分享］“微乐三打哈开挂辅...
［实测分享］“微乐三打哈开挂辅助神器”!揭秘曝光猫腻亲，微乐三打哈这个游戏其实有挂的，确实是有挂的，...
股东读长文批比亚迪存在营销等短...
6月6日上午，比亚迪2024年度股东大会上，一名股东在提问时读长文批比亚迪存在产品营销等方面的短板，...
重大通报“星悦陕西麻将究竟是不...
您好：星悦陕西麻将这款游戏可以开挂，确实是有挂的，需要软件加微信【69174242】，很多玩家在星悦...