深圳网站建设制作设计公司,html网站的上传,化妆品网站模板下载,海外网络推广定制673. 最长递增子序列的个数
链接: 673. 最长递增子序列的个数 给定一个未排序的整数数组 nums #xff0c; 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列#xff0c;分别是 [1, 3, 4,…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]
i. 我们此时已经知道 len[i] 的信息还知道 [0, i - 1] 区间上的 count[j] 信 息⽤ j 表⽰ [0, i - 1] 区间上的下标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(vectorint nums) {int nnums.size();vectorint dp(n,1),count(n,1);int Count1;int Max1;for(int i1;in;i){for(int j0;ji;j){if(nums[i]nums[j]){ if(dp[j]1dp[i]){count[i]count[j];}if(dp[j]1dp[i]){dp[i]dp[j]1;count[i]count[j];}}}if(Maxdp[i]) Countcount[i];if(Maxdp[i]) {Maxdp[i];Countcount[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(vectorvectorint pairs) {int npairs.size();sort(pairs.begin(),pairs.end());vectorint dp(n,1);int len1;for(int i1;in;i){for(int j0;ji;j){if(pairs[i][0]pairs[j][1]){dp[i]max(dp[i],dp[j]1);}}lenmax(len,dp[i]);}return len;}
