【算法挨揍日记】day31——673. 最长递增子序列的个数、646. 最长数对链

 673. 最长递增子序列的个数

673. 最长递增子序列的个数

题目解析：

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

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

解题思路：

算法思路：

1. 状态表⽰：

先尝试定义⼀个状态：以 i 为结尾的最⻓递增⼦序列的「个数」。那么问题就来了，我都不知道

以 i 为结尾的最⻓递增⼦序列的「⻓度」是多少，我怎么知道最⻓递增⼦序列的个数呢？

因此，我们解决这个问题需要两个状态，⼀个是「⻓度」，⼀个是「个数」：

len[i] 表⽰：以 i 为结尾的最⻓递增⼦序列的⻓度；

count[i] 表⽰：以 i 为结尾的最⻓递增⼦序列的个数。

2. 状态转移⽅程：

求个数之前，我们得先知道⻓度，因此先看 len[i] ：

i. 在求 i 结尾的最⻓递增序列的⻓度时，我们已经知道 [0, i - 1] 区间上的 len[j]

信息，⽤ j 表⽰ [0, i - 1] 区间上的下标；

ii. 我们需要的是递增序列，因此 [0, i - 1] 区间上的 nums[j] 只要能和 nums[i]

构成上升序列，那么就可以更新 dp[i] 的值，此时最⻓⻓度为 dp[j] + 1 ；

iii. 我们要的是 [0, i - 1] 区间上所有情况下的最⼤值。

综上所述，对于 len[i] ，我们可以得到状态转移⽅程为：

len[i] = max(len[j] + 1, len[i]) ，其中 0 <= j < i ，并且 nums[j] <

nums[i] 。

在知道每⼀个位置结尾的最⻓递增⼦序列的⻓度时，我们来看看能否得到 count[i] ：

i. 我们此时已经知道 len[i] 的信息，还知道 [0, i - 1] 区间上的 count[j] 信

息，⽤ j 表⽰ [0, i - 1] 区间上的下标；

ii. 我们可以再遍历⼀遍 [0, i - 1] 区间上的所有元素，只要能够构成上升序列，并且上

升序列的⻓度等于 dp[i] ，那么我们就把 count[i] 加上 count[j] 的值。这样循

环⼀遍之后， count[i] 存的就是我们想要的值。

综上所述，对于 count[i] ，我们可以得到状态转移⽅程为：

count[i] += count[j] ，其中 0 <= j < i ，并且 nums[j] < nums[i] &&

dp[j] + 1 == dp[i] 。

3. 初始化：

◦ 对于 len[i] ，所有元素⾃⼰就能构成⼀个上升序列，直接全部初始化为 1 ；

◦ 对于 count[i] ，如果全部初始化为 1 ，在累加的时候可能会把「不是最⼤⻓度的情况」累

加进去，因此，我们可以先初始化为 0 ，然后在累加的时候判断⼀下即可。具体操作情况看代

码~

4. 填表顺序：

毫⽆疑问是「从左往右」。

5. 返回值：

⽤ manLen 表⽰最终的最⻓递增⼦序列的⻓度。

根据题⽬要求，我们应该返回所有⻓度等于 maxLen 的⼦序列的个数。

 解题代码：

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n=nums.size();vector<int>dp(n,1);vector<int>f(n,1);int retlength=1;int retcount=1;for(int i=1;i<n;i++){//int length=f[0];//0到i-1区间内的最大长度for(int j=0;j<i;j++){if(nums[j]<nums[i]){       if(f[j]+1==f[i])dp[i]+=dp[j];else if(f[j]+1>f[i]){dp[i]=dp[j];f[i]=f[j]+1;}}  }if(retlength==f[i])retcount+=dp[i];else if(retlength<f[i]){retcount=dp[i];retlength=f[i];}}return retcount; }
};

646. 最长数对链

​​​​​​646. 最长数对链

题目描述：

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

解题思路：

算法思路：

这道题⽬让我们在数对数组中挑选出来⼀些数对，组成⼀个呈现上升形态的最⻓的数对链。像不像

我们整数数组中挑选⼀些数，让这些数组成⼀个最⻓的上升序列？因此，我们可以把问题转化成我

们学过的⼀个模型： 300. 最⻓递增⼦序列 。因此我们解决问题的⽅向，应该在「最⻓递增⼦序

列」这个模型上。

不过，与整形数组有所区别。在⽤动态规划结局问题之前，应该先把数组排个序。因为我们在计

算 dp[i] 的时候，要知道所有左区间⽐ pairs[i] 的左区间⼩的链对。排完序之后，只⽤

「往前遍历⼀遍」即可。

1. 状态表⽰：

dp[i] 表⽰以 i 位置的数对为结尾时，最⻓数对链的⻓度。

2. 状态转移⽅程：

对于 dp[i] ，遍历所有 [0, i - 1] 区间内数对⽤ j 表⽰下标，找出所有满⾜ pairs[j]

[1] < pairs[i][0] 的 j 。找出⾥⾯最⼤的 dp[j] ，然后加上 1 ，就是以 i 位置为结

尾的最⻓数对链。

3. 初始化：

刚开始的时候，全部初始化为 1 。

4. 填表顺序：

根据「状态转移⽅程」，填表顺序应该是「从左往右」。

5. 返回值：

根据「状态表⽰」，返回整个 dp 表中的最⼤值。

解题代码：

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(),pairs.end());int n=pairs.size();vector<int>dp(n,1);for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(pairs[j][1]<pairs[i][0])dp[i]=max(dp[i],dp[j]+1);}}int ret=1;for(int i=0;i<n;i++)ret=max(ret,dp[i]);return ret;}
};