【动态规划刷题 14】最长递增子序列的个数&& 最长数对链

简介: 【动态规划刷题 14】最长递增子序列的个数&& 最长数对链

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

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

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

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


示例 1:


输入: [1,3,5,4,7]

输出: 2

解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:


输入: [2,2,2,2,2]

输出: 5

解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。


1.状态表示*

我们解决这个问题需要两个状态,⼀个是「⻓度」,⼀个是「个数」:

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

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

2.状态转移方程

对于len[i],很容易可以得出其状态转移方程,可以参考之前的题解。

对于count[i]:

在知道每⼀个位置结尾的最⻓递增⼦序列的⻓度时,count[i] :

  1. i. 我们此时已经知道 len[i] 的信息,还知道 [0, i - 1] 区间上的 count[j] 信 息,⽤ j 表⽰ [0, i - 1] 区间上的下标;
  2. ii. 我们可以再遍历⼀遍 [0, i - 1] 区间上的所有元素,只要能够构成上升序列,并且上 升序列的⻓度等于 dp[i],那么我们就把 count[i] 加上 count[j] 的值。这样循 环⼀遍之后, count[i] 存的就是我们想要的值。

3. 初始化

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

◦ 对于 count[i] ,全部初始化为 1 ;

4. 填表顺序

显⽽易⻅,填表顺序「从左往右」

5. 返回值

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

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

代码:

 int findNumberOfLIS(vector<int>& nums) {
         int n=nums.size();
        vector<int> dp(n,1),count(n,1);
        int Count=1;
        int Max=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {  
                    if(dp[j]+1==dp[i])
                    {
                        count[i]+=count[j];
                    }
                    if(dp[j]+1>dp[i])
                    {
                        dp[i]=dp[j]+1;
                        count[i]=count[j];
                    }
                }
            }
            if(Max==dp[i]) Count+=count[i];
            if(Max<dp[i]) 
            {
                Max=dp[i];
                Count=count[i];
            } 
        }
        return Count;
    }

646. 最长数对链

链接: 646. 最长数对链

给你一个由 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] 。

示例 2:

输入:pairs = [[1,2],[7,8],[4,5]]

输出:3

解释:最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

解法思路

在⽤动态规划结局问题之前,应该先把数组排个序。因为我们在计算 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 表中的最⼤值

代码:

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

相关文章
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
|
算法 JavaScript Go
【动态规划】最长递增子序列
【动态规划】最长递增子序列
|
7月前
代码随想录 Day44 动规12 LeetCode T300 最长递增子序列 T674 最长连续递增序列 T718 最长重复子数组
代码随想录 Day44 动规12 LeetCode T300 最长递增子序列 T674 最长连续递增序列 T718 最长重复子数组
64 0
|
7月前
leetcode-646:最长数对链
leetcode-646:最长数对链
39 0
|
7月前
|
人工智能
leetcode-718:最长重复子数组
leetcode-718:最长重复子数组
50 0
|
算法 程序员 C#
C++二分查找算法的应用:最长递增子序列
C++二分查找算法的应用:最长递增子序列
|
算法
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
51 1
|
算法
【学会动态规划】最长递增子序列的个数(28)
【学会动态规划】最长递增子序列的个数(28)
49 0
|
机器学习/深度学习 人工智能 算法
代码随想录训练营day52| 300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组...
代码随想录训练营day52| 300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组...
|
人工智能
leetcode 718 最长重复子数组
leetcode 718 最长重复子数组
64 0
leetcode 718 最长重复子数组