求最长递增子序列个数——C++
声明：本文原题主要来自************************************************************力扣************************************************************** ，记录此博客主要是为自己学习总结，不做任何商业等活动！**
一、下面是原题描述
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 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。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
1.1题目分析
已有关于求最长上升子序列长度——C++的文章进行了详细探讨。而本题则关注的是寻找最长增长子序列的数量。通过进一步分析发现,本题与经典的LIS（Longest Increasing Subsequence）问题具有相似性，在解决方法上也采用了类似的框架和算法策略，并在此基础上增加了对每个可能的最小子序列数量进行记录的能力
用maxLen来存储每个dp[i]所对应的最长子序列长度，并用count[i]来存储对应的最大子序列数量；其中i代表数组中元素的数量，并且满足0 ≤ i < n；计算其在i-1位置处的状态后，则可以进一步推导得到所需的结果
dp[i] = max(dp[j]) + 1，满足条件nums[i] > nums[j]，0 =< i < n，0 <= j < i - 1；
当nums[i] > nums[j]时，有：
- 如果dp[i] == dp[j] + 1，则count[i] += count[j]；
- 如果dp[i] < dp[j] + 1，则count[i] = count[j]；
第1处需要累加的原因是由于之前遇到了一个同样长度的最长子序列，并因此将此子序列也加入到计算中。在随后的处理中为何要重新赋值的原因是最初发现了一个较长的子序列，并因此必须更新count[i]所记录的最长子序列长度
当计算得出所有的count[i]之后，在遍历查找所有等于最大长度maxLen的count[j]时，在将这些满足条件的count[j]相加即可得到最长子序列的长度asn。
动态规划需遵循三个必要条件：状态方程、状态转移方程及边界条件。经分析可知该问题符合所有必要条件。以下将列出相关情况的表格进行详细说明
将数值列表nums初始化为{..., ...}。
对于每个索引i（其中i的取值范围为0到n-1），计算dp数组中的第i个元素：
该元素表示从数组前i项中选择一个递增子序列的最大长度。
具体计算方法如下：
当当前元素nums[i]>之前某个元素numsj时，
则有以下两种情况：
第一种情况：如果当前元素对应的最长递增子序列长度（即dp[i）比以j结尾的情况多一项（即dp[j]+1），那么将j结尾的所有可能情况的数量加到当前i的位置上。
第二种情况：如果当前元素对应的最长递增子序列长度（即dp[i）比以j结尾的情况少一项（即小于等于），那么直接复制以j结尾的数量到当前i的位置上。
元素下标n 0 1 2 3 4 5 6 7 元素值 10 9 2 5 3 7 101 18 dpi 1 1 1 2 2 3 4 4 count 1 2 3 1 2 2 2 4
1.2代码实现分析
1.2.1求出dp[i]和count[i]的值
当nums[i]>nums[j]时，则更新dp_i和count_i。其更新规则为：当dp_i < dp_j + 1时，则设置为 dp_i = dp_j + 1，并令 count_i = count_j。这两条逻辑判断是基于若当前最长子序列长度大于现有记录的情况。通常情况下，在首次遇到比现有最长子序列还长的情况时,count_i会被置为1。仅在后续遍历中再次遇到相同长度的最长子序列时,才会执行累加操作,即令 count_i += count_j. 关键实现代码如下：
for (int i = 0; i < size; ++i) // 求出前面i个dp[i]和count[i]的值
{
dp[i] = 1;
count[i] = 1;
for (int j = 0; j < i; ++j) // 更新dp[i]和count[i]
{
if (nums[i] > nums[j])
{
if (dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
count[i] = count[j];
}
else if (dp[i] == dp[j] + 1)
{
count[i] += count[j];
}
}
}
// 根据已求得的dp[i]和count[i]，求出asn
}1.2.2根据已求得的dp[i]和count[i]求出asn
基于之前更新的dp[i]和count[i]值，请计算并确定最长子序列的长度asn。具体来说：
- 如果出现新增的最大长度情况，则请直接将asn设为当前count[i]值。
- 否则，在存在与当前maxLen相同的最大长度时，请累加所有对应的最长子序列数量到asn中。
关键代码如下：
for (int i = 0; i < size; ++i) // 大遍历
{
dp[i] = 1;
count[i] = 1;
for (int j = 0; j < i; ++j) // 小遍历，更新dp[i]和count[i]
{
// ......
}
if (dp[i] > maxLen) // 假如有新增最长子序列，则直接更新
{
maxLen = dp[i];
asn = count[i];
}
else if (dp[i] == maxLen) // 否则有相等最长子序列，则累加所有相同子序列count[i]
{
asn += count[i];
}
}1.3完整代码
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int asn=0, maxLen=1, size = nums.size();
vector<int> dp(size, 0), count(size, 0);
for(int i=0; i<size; ++i) // 大遍历
{
dp[i] = 1;
count[i] = 1;
for(int j=0; j<i; ++j) // 小遍历，更新dp[i]和count[i]
{
if(nums[i] > nums[j]) // 出现更新子序列
{
if(dp[i] < dp[j] + 1) // 更新最长子序列长度
{
dp[i] = dp[j] + 1;
count[i] = count[j];
}
else if(dp[i] == dp[j] + 1) // 出现相同最长子序列长度，累加所有相同最长子序列
{
count[i] += count[j];
}
}
}
if(dp[i] > maxLen) // 更新完后找出最长子序列dp[i]，大于maxLen则更新，否则累加
{
maxLen = dp[i];
asn = count[i];
}
else if(dp[i] == maxLen) // 遇到相同最长子序列，需要累加所有相同最长子序列
{
asn += count[i];
}
}
return asn;
}
};1.4结果
1.5复杂度分析
通过上述代码可以看出，在算法运行过程中经历了双重循环结构；该算法每执行一次迭代运算都会创建一个占用n个元素存储空间的一维数组，并且在每次迭代结束后都需要释放该数组占用的空间资源以避免内存泄漏问题；因此从计算资源消耗的角度而言其时间复杂度为二次方级别而空间复杂度与问题规模成正比关系