673. 最长递增子序列的个数

 1 class Solution 
 2 {
 3 public:
 4     int findNumberOfLIS(vector<int>& nums) 
 5     {
 6         if(nums.size() == 0) return 0;
 7         int n = nums.size();
 8         vector<int> dp(n,1);
 9         vector<int> count(n,1);//以当前数结尾的组合数
10         int res = dp[0];
11         int ans = 0;
12         for(int i = 0;i < n;i ++)
13         {
14             for(int j = 0;j < i;j ++)
15             {
16                 if(nums[i] > nums[j]) 
17                 {
18                     if(dp[i] < dp[j] + 1)
19                     {
20                         dp[i] = dp[j] + 1;
21                         count[i] = count[j];
22                     }
23                     //dp[i]比dp[j]多1，说明dp[j]有重合数
24                     else if(dp[i] == dp[j] + 1) count[i] += count[j];
25                 } 
26             }
27             if(res < dp[i]) res = dp[i];
28         }
29         for(int i = 0;i < n;i ++)
30         {
31             if(dp[i] == res) ans += count[i];
32         }
33         return ans;
34     }
35 };