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;
}
};
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/280225.html