自建wordpress主题,深圳网站建设公司乐云seo598,汽车网站网页模板,宁夏网站设计300.最长递增子序列
题目链接#xff1a;https://leetcode.com/problems/longest-increasing-subsequence
解法#xff1a;
1. dp[i]的定义
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。
2. 状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置…300.最长递增子序列
题目链接https://leetcode.com/problems/longest-increasing-subsequence
解法
1. dp[i]的定义
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。
2. 状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值。
所以if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1)。
3. dp[i]的初始化
每一个i对应的dp[i]即最长递增子序列起始大小至少都是1. 所以都初始化为1.
这道题的写法上为啥dp[-1] 不直接取为最大值呢因为dp[i]是以nums[i]结尾的最长而以最后一个元素结尾的子序列不一定长度最长。
边界条件无
时间复杂度O(nlogn)
空间复杂度O(n) class Solution(object):def lengthOfLIS(self, nums):if len(nums) 1:return 1dp [1] * len(nums)for i in range(1, len(nums)):for j in range(0, i):if nums[i] nums[j]:dp[i] max(dp[i], dp[j]1)# 注意dp[i]定义为以num[i]结尾的最长那么处理结束后# 不一定就是dp[-1]是最长比如[1,2,3,4,2,1]return max(dp) 674. 最长连续递增序列 题目链接https://leetcode.com/problems/longest-increasing-subsequence 解法 1. 确定dp的含义 dp[i]以num下标i元素为结尾的连续递增的子序列长度为dp[i]。 2. 确定递推公式 如果 nums[i] nums[i - 1]那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 1 。 即dp[i] dp[i - 1] 1; 注意这里就体现出和动态规划300.最长递增子序列 (opens new window)的区别 因为本题要求连续递增子序列所以就只要比较nums[i]与nums[i - 1]而不用去比较nums[j]与nums[i] j是在0到i之间遍历。 既然不用j了那么也不用两层for循环本题一层for循环就行比较nums[i] 和 nums[i - 1]。 最后一定需要说明的是返回值是max(dp)而不是dp[-1]因为以最后一个元素结尾的最长连续子序列不一定是最长的可能以中间某个元素结尾的最长连续子序列才是最长的。 边界条件无 时间复杂度O(n) 空间复杂度O(n) class Solution(object):def findLengthOfLCIS(self, nums):dp [1] * len(nums)for i in range(1, len(nums)):if nums[i] nums[i-1]:dp[i] dp[i-1] 1# dp[i] 表示以num[i]结尾的最长子序列的长度# 所以dp[-1]不一定是最长的return max(dp) 718. 最长重复子数组 题目链接https://leetcode.com/problems/maximum-length-of-repeated-subarray 解法 1. 确定dp数组dp table以及下标的含义 dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]。 特别注意 “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 2. 确定递推公式 根据dp[i][j]的定义dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。即当A[i - 1] 和B[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1; 根据递推公式可以看出遍历i 和 j 要从1开始 3. dp数组如何初始化 根据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。 4. 结果的返回 dp[-1][-1] 不一定是最大值所以在循环的过程中不断更新最大值。 边界条件无 时间复杂度O(nm) 空间复杂度O(nm) class Solution(object):def findLength(self, nums1, nums2):dp [[0] * (len(nums2)1) for _ in range(len(nums1)1)]result 0for i in range(1, len(nums1)1):for j in range(1, len(nums2)1):# dp[i][j]表示A以下标(i-1)的字符串结尾# B以下标(j-1)结尾的最长重复子串长度if nums1[i-1] nums2[j-1]:dp[i][j] dp[i-1][j-1]1result max(result, dp[i][j])return result
