本文主要是介绍每日OJ题_子序列dp③_力扣673. 最长递增子序列的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
力扣673. 最长递增子序列的个数
解析代码
力扣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 <= nums.length <= 2000-10^6 <= nums[i] <= 10^6
class Solution {
public:int findNumberOfLIS(vector<int>& nums) {}
};解析代码
尝试定义一个状态：以 i 为结尾的最长递增子序列的「个数」。那么问题就来了，我都不知道 以 i 为结尾的最长递增子序列的长度是多少，我怎么知道最长递增子序列的个数呢？ 因此解决这个问题需要两个状态，一个是长度，一个是个数：
- len[i] 表示：以 i 为结尾的最长递增子序列的长度。
- count[i] 表示：以 i 为结尾的最长递增子序列的个数。
状态转移方程： 求个数之前得先知道长度，因此先看 len[i] ：
在求 i 结尾的最长递增序列的长度时，我们已经知道 [0, i - 1] 区间上的 len[j] 信息，用 j 表示 [0, i - 1] 区间上的下标。
我们需要的是递增序列，因此 [0, i - 1] 区间上的 nums[j] 只要能和 nums[i] 构成上升序列，那么就可以更新 dp[i] 的值，此时最长长度为 dp[j] + 1 ;
我们要的是 [0, i - 1] 区间上所有情况下的最大值。 综上所述，对于 len[i] ，我们可以得到状态转移方程为： len[i] = max(len[j] + 1, len[i]) ，其中 0 <= j < i ，并且 nums[j] < nums[i] 。
在知道每一个位置结尾的最长递增子序列的长度时，来看看能否得到 count[i] ：
此时已经知道 len[i] 的信息，还知道 [0, i - 1] 区间上的 count[j] 信 息，用 j 表示 [0, i - 1] 区间上的下标。可以再遍历一遍 [0, i - 1] 区间上的所有元素，只要能够构成上升序列，并且上升序列的长度等于 dp[i] ，那么就把 count[i] 加上 count[j] 的值。这样循环一遍之后， count[i] 存的就是我们想要的值。
综上所述，对于 count[i] ，我们可以得到状态转移方程为： count[i] += count[j] ，其中 0 <= j < i ，并且 nums[j] < nums[i] && len[j] + 1 == len[i] 。
如果len[j] + 1 > len[i]，len[i] = len[j] + 1，count[i] = count[j]。
初始化、填表顺序、返回值：
对于 len[i] 和count[i] ，所有元素自己就能构成一个上升序列，直接全部初始化为 1。
从左往右填表，最后返回len表最大的元素的最大个数。
class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();vector<int> len(n, 1), count(n, 1);// len[i] 表示：以 i 为结尾的最长递增子序列的长度。// count[i] 表示：以 i 为结尾的最长递增子序列的个数。int retLen = 1, retCount = 1; // 记录最终结果for(int i = 1; i < n; ++i){for(int j = 0; j < i; ++j){if(nums[j] < nums[i]) // 是递增序列{if(len[j] + 1 == len[i]) // 长度一样，加等个数count[i] += count[j];else if(len[j] + 1 > len[i]) // 最长长度换了，重新计数len[i] = len[j] + 1, count[i] = count[j];}}if(retLen == len[i]) // 长度一样，加等个数retCount += count[i];else if(retLen < len[i]) // 最长长度换了，重新计数retLen = len[i], retCount = count[i];}return retCount;}
};这篇关于每日OJ题_子序列dp③_力扣673. 最长递增子序列的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
