673. Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
vector<vector<int>> dp;
int LIS(vector<int>& nums) {
vector<int> lis;
for(auto& n : nums) {
if(lis.empty() or lis.back() < n) {
lis.push_back(n);
} else {
auto p = lower_bound(lis.begin(),lis.end(),n);
*p = n;
}
}
return lis.size();
}
int helper(vector<int>& nums, int p, int k) {
if(k == 0) return 1;
if(p == nums.size()) return 0;
if(dp[p][k] != -1) return dp[p][k];
dp[p][k] = 0;
for(int i = p + 1; i <= nums.size() - k; i++) {
if(nums[p] < nums[i])
dp[p][k] += helper(nums,i,k-1);
}
return dp[p][k];
}
public:
int findNumberOfLIS(vector<int>& nums) {
int len = LIS(nums), n = nums.size(), res = 0;
dp = vector<vector<int>>(n, vector<int>(len, -1));
for(int i = 0; i <= nums.size() - len; i++)
res += helper(nums,i,len - 1);
return res;
}
};
|
