文章目录一、最长递增子序列解题思路代码实现及解析总结二、最长递增子序列的个数解题思路代码实现及解析总结三、最长数对链解题思路四、最长的斐波那契子序列的长度解题思路代码实现及解析总结一、最长递增子序列Leetcode链接给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。解题思路跟【子数组问题】其实是大差不差的只是状态转移方程稍微不一样因为子数组是连续的数组片段而【子序列问题】是数组的子集是由数组中的数据挑出来一些并保持数据之间的相对位置不变而得出的序列所以它所形成的情况是一定比子数组多的状态表示dp[i]表示以i位置为结尾的所有的递增子序列中最长的递增子序列的长度而要计算dp[i]时nums[i]可以单独组成一个递增子序列也可以选择和它前面的递增子序列dp[j]0ji组合为一个新的递增子序列这样也就和以前一样形成了递归子问题只不过【子数组问题】中nums[i]只会和dp[i-1]进行组合而到了【子序列问题】nums[i]就可以和dp[j] (0ji)尝试进行多种组合然后从这些组合中挑选出最合适的那个就是dp[i]最终的结果了所以本题的状态转移方程当nums[i]单独组成一个递增子序列时dp[i]的值就为1当它与前面的组合时if(nums[i]nums[j]) dp[i]dp[j]1;当nums[i]nums[j]时才可与dp[j]组成一个新的递增子序列而在循环中会进行多次 if 判断得出多个组合找出最长的那个就是dp[i]最终的值代码实现及解析classSolution{publicintlengthOfLIS(int[]nums){intnnums.length;int[]dpnewint[n];Arrays.fill(dp,1);//可以先把dp表全初始化为1//填表intretdp[0];for(inti1;in;i){//外循环每次进行dp[i]的计算由内循环不断去尝试多种组合而计算出正确答案for(intji-1;j0;j--){//内循环进行多次遍历寻找i位置与它前面的哪个子序列进行匹配最合适递增子序列最长if(nums[i]nums[j])dp[i]Math.max(dp[i],dp[j]1);}retMath.max(ret,dp[i]);}returnret;}}总结复习解题思路看代码中的两个循环和注释其他的【子序列问题】都是以其为基础的二、最长递增子序列的个数Leetcode链接给定一个未排序的整数数组 nums 返回最长递增子序列的个数 。注意 这个数列必须是 严格 递增的。解题思路本题与上题思路一样但是多了个对最值个数的统计使用了一个“小贪心”的算法如何在只遍历一遍的前提下找出数组中最值的个数我们采用一个贪心的思路对数据的处理进行分类讨论以找最大值个数为例先假设在遇到更大的数据之前目前遍历到的就是最大值我们直接进行计数在遇到更大的数值之后再重新计数于是有一下代码intmaxVal,count;for(inti0;in;i){if(nums[i]maxVal){maxValnums[i];//更新最大值count0;//重新计数}elseif(nums[i]maxVal){count;//对该最值继续进行累加计数}}//最终遍历完数组也就找到了最值的个数在沿用之前解题思路的同时使用该小算法对最长递增子序列的个数进行统计代码实现及解析classSolution{publicintfindNumberOfLIS(int[]nums){intnnums.length;int[]lennewint[n];int[]countnewint[n];for(inti0;in;i)len[i]count[i]1;//dp表的初始化像这种dp表的值至少为1的都可以直接先初始化为1然后在后续填表中就不用再考虑值为1的这种情况了//填表intretLen1,retCount1;//这里一定要初始化为1不然就漏掉了0位置的值这是dp问题中常会出现的一个问题由于我们的填表是从下标1位置开始的所以在循环外面定义变量要注意如果要在循环里面使用的话可能会出现这样的初始化问题for(inti1;in;i){for(intji-1;j0;j--){//第一次“小贪心”算法在像以前一样筛选出最大的len[i]值的同时将最大的len值的个数也统计出if(nums[j]nums[i]){if(len[j]1len[i]){//找到了一个新的最大值len[i]len[j]1;//更新len[i]的最大值count[i]count[j];//重新对此最值进行计数}elseif(len[j]1len[i]){count[i]count[j];//对该最大len值继续进行累计计数注意在本题中count可不是}}}//第二次“小贪心”算法内层for循环结束后dp[i]也就填好了我们再直接对dp表使用这个小算法来找出最终的最大值的个数if(len[i]retLen){retLenlen[i];retCountcount[i];}elseif(len[i]retLen){retCountcount[i];}}returnretCount;}}总结复习解题思路和代码注释注释中有不少dp题目常见的细节问题三、最长数对链Leetcode链接给你一个由 n 个数对组成的数对数组 pairs 其中 pairs[i] [lefti, righti] 且 lefti righti 。现在我们定义一种 跟随 关系当且仅当 b c 时数对 p2 [c, d] 才可以跟在 p1 [a, b] 后面。我们用这种形式来构造 数对链 。其实就是构造递增序列找出并返回能够形成的 最长数对链的长度 。你不需要用到所有的数对你可以以任何顺序选择其中的一些数对来构造。示例 1输入pairs [[1,2], [2,3], [3,4]]输出2解释最长的数对链是 [1,2] - [3,4] 。解题思路这题乍一看跟第一题【最长递增子序列】是几乎一样的但是当我们定义状态表示为dp[i]表示以 i 位置为结尾的所有子数对链中最长的子数对链的长度我们发现虽然状态表示规定以 i 位置为结尾但按题意完全可以在 i 位置后面找个合法的数对放到 i 位置前面进行组合那这题就没法做了所以我们可以先按数对的第一个元素的大小对所有的数对进行排序所以就变成了和【最长递增子序列】一样了只需要在 i 位置前面找数对进行组合所以再次认识到在特殊情况下对数据进行排序会有多大的作用四、最长的斐波那契子序列的长度Leetcode链接如果序列 x1, x2, …, xn 满足下列条件就说它是 斐波那契式 的n 3对于所有 i 2 n都有 xi xi1 xi2给定一个 严格递增 的正整数数组形成序列 arr 找到 arr 中最长的斐波那契式的子序列的长度。如果不存在返回 0 。解题思路本题如果还像之前一样使用dp[i]表示以 i 位置为结尾的最长的斐波那契子序列这样的状态表示是不行的因为这样无法提供足够的信息去描述一个斐波那契子序列的特征只知道这个序列是以那个元素结尾的不知道它长什么样子也就是已知的信息不足以推导出这个序列继而无法推导出一个状态转移方程对于类似这样的题我们应该换一种状态表示方法使其能够反映出足够的信息来描述所代表的斐波那契子序列。那么这时我们可以采用两个元素的定位来进行状态表示dp[i][j] 表示以 i 、j 位置元素为结尾分别为倒数后两个元素nums[i]bnums[j]ci j的斐波那契子序列。这样就可以正确地推出状态转移方程了有 b、c 两个元素我们就可以直接推导出倒数第三个元素 a ac-b 找到 a 元素的位置 k 就可以推导出正确的状态转移方程但是对于 a 的位置我们要进行分类讨论对于这种根据两个元素进行状态表示的定位的题目比如一会要拓展介绍的【最⻓等差数列】当我们根据这两个元素进行其他元素的计算的时候对于该元素的位置情况一定要分类讨论对于2、3两种情况我们虽然把dp表初始化为2是一个不合法的值本题合法子序列的长度n3但由于dp表后续位置的填表要用到这些位置所以还是要初始化为2到了最后记录返回值的时候自动筛选这些不合法的值就行而这其实也就是dp表的初始化和之前一样dp表最差也得是这种情况dp表的值至少为2所以直接初始化为2之后就不用再考虑这两种情况了另外寻找 a 的位置的时候不要再重新遍历一遍数据了这样时间复杂度将从O(n2)—O(n3)所以可以先把元素与它的下标绑定放到hash表中之后便于查找注意本题的数据是严格递增的题目中有所以不存在重复的数据对于 a 位置的查找不会出现干扰代码实现及解析classSolution{publicintlenLongestFibSubseq(int[]arr){MapInteger,IntegermapnewHashMap();intnarr.length;for(inti0;in;i){//把元素与其下标绑定方便之后更快地查找map.put(arr[i],i);}int[][]dpnewint[n][n];//二维dp表for(inti0;in;i)Arrays.fill(dp[i],2);//先把dp表初始化为2//填表intmaxLen2;for(inti1;in;i){//分别固定子序列的最后两个元素for(intji1;jn;j){intxarr[j]-arr[i];//由子序列的最后两个元素计算出倒数第三个数//如果不使用哈希表的话就要在下面重新遍历一遍前面的数据查找x时间复杂度将从O(n^2)—O(n^3)if(map.containsKey(x)map.get(x)i){//如果存在x元素且x在i位置前面合法构成一个斐波那契子序列dp[i][j]dp[map.get(x)][i]1;//将dp[i][j]的初始值更新maxLenMath.max(maxLen,dp[i][j]);}}}returnmaxLen2?0:maxLen;//这里不要忘了maxLen可能为2这种情况是错误的要手动返回0}}总结复习解题思路和代码注释扩展类似题目【最长等差数列】Leetcode链接给你一个整数数组 nums返回 nums 中最长等差子序列的长度。回想一下nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[ik] 且 0 i1 i2 … ik nums.length - 1。并且如果 seq[i1] - seq[i]( 0 i seq.length - 1) 的值都相同那么序列 seq 是等差的。解题思路那么本题与上题其实是一样的采用两个元素进行状态表示的定位对计算得出的新元素的位置进行分类讨论来推导状态转移方程但是该题的数据可不是严格递增的所以包含重复元素所以要解决重复元素查找时的问题其实像本题这种以及上题即使带有重复元素的版本的题目我们可以发现如果要寻找最长的子序列对于众多重复的 a只需让i、j 两个位置i j的元素与“离 i 位置最近的”那个 a 进行结合就一定是最长的那种情况因为前面的那些 a 只有可能在往前收缩的过程中丢失掉一些关键数据而使子序列长度减小所以我们只需要在 i 位置往后枚举的过程中不断将 i 之前已遍历过的元素加入hash表中再在hash表中查找时一定就是“离 i 位置最近的”那个 a因为hash表的put()函数会覆盖掉重复的key值只保留最新的。以上是对时间复杂度的优化若不做优化就要再从头开始遍历一遍数组找到 a 的位置时间复杂度就变为了O(n3) 当然要使用上面这种方法就必须使用“外循环从前往后固定 i 的位置内循环从i1位置开始固定 j 的位置”这样的枚举方式才可以在每次 i 往后走一步就put()一个新元素。另一个“外循环从前往后固定 j 的位置内循环在 0~(j-1) 范围内固定 i 的位置”这样的枚举方式就不可以因为i一直在往回蹦无法满足put()进的元素为“离 i 位置最近的且在 i 前面的”