一站式网站,连锁门店管理系统,赣州经济,用ps做个人网站界面673. 最长递增子序列的个数 673. 最长递增子序列的个数
题目解析#xff1a;
给定一个未排序的整数数组 nums #xff0c; 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
解题思路#xff1a; 算法思路#xff1a; 1. 状态表⽰#xff1a; 先尝试… 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(vectorint nums) {int nnums.size();vectorintdp(n,1);vectorintf(n,1);int retlength1;int retcount1;for(int i1;in;i){//int lengthf[0];//0到i-1区间内的最大长度for(int j0;ji;j){if(nums[j]nums[i]){ if(f[j]1f[i])dp[i]dp[j];else if(f[j]1f[i]){dp[i]dp[j];f[i]f[j]1;}} }if(retlengthf[i])retcountdp[i];else if(retlengthf[i]){retcountdp[i];retlengthf[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(vectorvectorint pairs) {sort(pairs.begin(),pairs.end());int npairs.size();vectorintdp(n,1);for(int i1;in;i){for(int j0;ji;j){if(pairs[j][1]pairs[i][0])dp[i]max(dp[i],dp[j]1);}}int ret1;for(int i0;in;i)retmax(ret,dp[i]);return ret;}
};
