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]
相关内容
热门资讯
朴朴超市进入线下开店：做流量，...
交流朴朴超市，实名添加微信lihua759321进群继叮咚买菜、小象超市后，前置仓生鲜赛道的另一大玩...
直面不确定性：中国银行业于挑战...
全文共4585字，阅读全文约需14分钟直面不确定性：中国银行业于挑战中寻成长（附21世纪金融年会议程...
国产替代与数字化转型下 中证软...
《金证研》 巽风/作者近日，国务院办公厅印发《关于加快场景培育和开放推动新场景大规模应用的实施意见》...
港股突发！刚刚，重大调整！ 港...
11月21日晚间消息，恒生指数公司发布季检结果，多个指数的成份股将有调整。根据公告，恒生科技指数纳入...
欧盟脸丢大了，27打1告败，俄...
俄乌冲突丢脸的不是乌克兰，而应该是欧盟，数量上是27打1，俄罗斯还一直被各种制裁，结果乌克兰的领土却...