Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Solution
我们需要求出最长长度序列的个数。不妨用两个数组 \(dp1, dp2\). 其中 \(dp1[i]\) 表示以 \(i\) 结尾的最长递增序列的长度， \(dp2[i]\) 表示以 \(i\) 结尾的最长递增序列的个数。
对于转移，\(dp1[i]\) 和前面一题一样:
\[dp1[i] = dp1[j]+1, \text{if }nums[j]<nums[i] \]对于 \(dp2[i]\):
\[dp2[i]=dp2[j], \text{if }nums[j]<nums[i] \]因为此时添加在 \(j\) 的末尾时，答案不变（直接继承前面的）
如果当前的 \(dp[j]+1=dp[i]\), 说明此时可以添加答案：
\[dp2[i]=dp2[i]+dp2[j] \]点击查看代码
class Solution {
private:
int dp1[2002];// length of lis
int dp2[2002];// num of lis
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n;i++)dp1[i]=dp2[i]=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
if(dp1[j]+1>dp1[i]){
dp1[i] = 1+dp1[j];
dp2[i] = dp2[j];
}
else if(dp1[j]+1==dp1[i]){
dp2[i]+=dp2[j];
}
}
}
}
int maxv = 0;
for(int i=0;i<n;i++)maxv=max(maxv,dp1[i]);
int ans=0;
for(int i=0;i<n;i++){
if(maxv==dp1[i])ans+=dp2[i];
}
return ans;
}
};