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

悠悠 2024-02-18 11:47 80阅读 0赞

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

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

### 题目解析： ###

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

**注意** 这个数列必须是 **严格** 递增的。![c5e7ba5127f246408681f80a03e45392.png][]

### 解题思路： ###

算法思路：

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. 最长数对链][646.]

### 题目描述： ###

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

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

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

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

### 解题思路： ###

算法思路：

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

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

们学过的⼀个模型：  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;
        }
    };

[673.]: https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
[c5e7ba5127f246408681f80a03e45392.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/4e5b2202fd9b4e1282d0e64600d35ba3.png
[646.]: https://leetcode.cn/problems/maximum-length-of-pair-chain/
[8e485cf75579460abc17eab5307ff317.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/c72ab4b7e5504b3cbd6165a0cc09acee.png