【动态规划算法】专题五——子序列问题

一、最长递增子序列

Leetcode链接
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解题思路

• 跟【子数组问题】其实是大差不差的，只是状态转移方程稍微不一样，因为子数组是连续的数组片段，而【子序列问题】是数组的子集，是由数组中的数据挑出来一些并保持数据之间的相对位置不变而得出的序列，所以它所形成的情况是一定比子数组多的
• 状态表示：dp[i]表示以i位置为结尾的所有的递增子序列中最长的递增子序列的长度
• 而要计算dp[i]时，nums[i]可以单独组成一个递增子序列，也可以选择和它前面的递增子序列（dp[j]，0<=j<i）组合为一个新的递增子序列（这样也就和以前一样形成了递归子问题），只不过【子数组问题】中nums[i]只会和dp[i-1]进行组合，而到了【子序列问题】，nums[i]就可以和dp[j] (0<=j<i)，尝试进行多种组合，然后从这些组合中挑选出最合适的那个就是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){intn=nums.length;int[]dp=newint[n];Arrays.fill(dp,1);//可以先把dp表全初始化为1//填表：intret=dp[0];for(inti=1;i<n;i++){//外循环：每次进行dp[i]的计算，由内循环不断去尝试多种组合而计算出正确答案for(intj=i-1;j>=0;j--){//内循环：进行多次遍历，寻找i位置与它前面的哪个子序列进行匹配最合适（递增子序列最长）if(nums[i]>nums[j])dp[i]=Math.max(dp[i],dp[j]+1);}ret=Math.max(ret,dp[i]);}returnret;}}

总结

• 复习解题思路，看代码中的两个循环和注释，其他的【子序列问题】都是以其为基础的

二、最长递增子序列的个数

Leetcode链接
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

解题思路

• 本题与上题思路一样，但是多了个对最值个数的统计，使用了一个“小贪心”的算法：

如何在只遍历一遍的前提下找出数组中最值的个数？

• 我们采用一个贪心的思路对数据的处理进行分类讨论（以找最大值个数为例），先假设在遇到更大的数据之前，目前遍历到的就是最大值，我们直接进行计数，在遇到更大的数值之后再重新计数，于是有一下代码：

intmaxVal,count;for(inti=0;i<n;i++){if(nums[i]>maxVal){maxVal=nums[i];//更新最大值count=0;//重新计数}elseif(nums[i]==maxVal){count++;//对该最值继续进行累加计数}}//最终遍历完数组也就找到了最值的个数

• 在沿用之前解题思路的同时，使用该小算法对最长递增子序列的个数进行统计

代码实现及解析

classSolution{publicintfindNumberOfLIS(int[]nums){intn=nums.length;int[]len=newint[n];int[]count=newint[n];for(inti=0;i<n;i++)len[i]=count[i]=1;//dp表的初始化（像这种dp表的值至少为1的都可以直接先初始化为1，然后在后续填表中就不用再考虑值为1的这种情况了）//填表：intretLen=1,retCount=1;//这里一定要初始化为1不然就漏掉了0位置的值，这是dp问题中常会出现的一个问题，由于我们的填表是从下标1位置开始的所以在循环外面定义变量要注意如果要在循环里面使用的话可能会出现这样的初始化问题for(inti=1;i<n;i++){for(intj=i-1;j>=0;j--){//第一次“小贪心”算法（在像以前一样筛选出最大的len[i]值的同时将最大的len值的个数也统计出）：if(nums[j]<nums[i]){if(len[j]+1>len[i]){//找到了一个新的最大值len[i]=len[j]+1;//更新len[i]的最大值count[i]=count[j];//重新对此最值进行计数}elseif(len[j]+1==len[i]){count[i]+=count[j];//对该最大len值继续进行累计计数（注意在本题中count可不是++）}}}//第二次“小贪心”算法（内层for循环结束后dp[i]也就填好了，我们再直接对dp表使用这个小算法来找出最终的最大值的个数）：if(len[i]>retLen){retLen=len[i];retCount=count[i];}elseif(len[i]==retLen){retCount+=count[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 + xi+1 == xi+2
给定一个 严格递增 的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果不存在，返回 0 。

解题思路

• 本题如果还像之前一样使用：dp[i]表示以 i 位置为结尾的最长的斐波那契子序列，这样的状态表示是不行的，因为这样无法提供足够的信息去描述一个斐波那契子序列的特征（只知道这个序列是以那个元素结尾的，不知道它长什么样子，也就是已知的信息不足以推导出这个序列），继而无法推导出一个状态转移方程

• 对于类似这样的题我们应该换一种状态表示方法，使其能够反映出足够的信息来描述所代表的斐波那契子序列。那么这时我们可以采用两个元素的定位来进行状态表示：dp[i][j] 表示以 i 、j 位置元素为结尾（分别为倒数后两个元素nums[i]=b，nums[j]=c，i < j）的斐波那契子序列。这样就可以正确地推出状态转移方程了，有 b、c 两个元素我们就可以直接推导出倒数第三个元素 a ，a=c-b， 找到 a 元素的位置 k 就可以推导出正确的状态转移方程，但是对于 a 的位置我们要进行分类讨论（对于这种根据两个元素进行状态表示的定位的题目，比如一会要拓展介绍的【最⻓等差数列】，当我们根据这两个元素进行其他元素的计算的时候，对于该元素的位置情况一定要分类讨论）：
  

• 对于2、3两种情况，我们虽然把dp表初始化为2是一个不合法的值（本题合法子序列的长度n>=3），但由于dp表后续位置的填表要用到这些位置，所以还是要初始化为2，到了最后记录返回值的时候自动筛选这些不合法的值就行（而这其实也就是dp表的初始化，和之前一样，dp表最差也得是这种情况，dp表的值至少为2，所以直接初始化为2，之后就不用再考虑这两种情况了）

• 另外寻找 a 的位置的时候不要再重新遍历一遍数据了，这样时间复杂度将从O(n²)—>O(n³)，所以可以先把元素与它的下标绑定放到hash表中，之后便于查找，注意本题的数据是严格递增的（题目中有），所以不存在重复的数据，对于 a 位置的查找不会出现干扰

代码实现及解析

classSolution{publicintlenLongestFibSubseq(int[]arr){Map<Integer,Integer>map=newHashMap<>();intn=arr.length;for(inti=0;i<n;i++){//把元素与其下标绑定，方便之后更快地查找map.put(arr[i],i);}int[][]dp=newint[n][n];//二维dp表for(inti=0;i<n;i++)Arrays.fill(dp[i],2);//先把dp表初始化为2//填表：intmaxLen=2;for(inti=1;i<n;i++){//分别固定子序列的最后两个元素for(intj=i+1;j<n;j++){intx=arr[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]的初始值更新maxLen=Math.max(maxLen,dp[i][j]);}}}returnmaxLen==2?0:maxLen;//这里不要忘了，maxLen可能为2，这种情况是错误的要手动返回0}}

总结

• 复习解题思路和代码注释

扩展类似题目：

【最长等差数列】
Leetcode链接
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], …, nums[i_k] ，且 0 <= i1 < i2 < … < i_k<= nums.length - 1。并且如果 seq[i+1] - 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(n³) ）
• 当然要使用上面这种方法，就必须使用“外循环从前往后固定 i 的位置，内循环从i+1位置开始固定 j 的位置”这样的枚举方式才可以，在每次 i 往后走一步就put()一个新元素。另一个“外循环从前往后固定 j 的位置，内循环在 0~(j-1) 范围内固定 i 的位置”这样的枚举方式就不可以，因为i一直在往回蹦，无法满足put()进的元素为“离 i 位置最近的，且在 i 前面的”