# LC 673. Number of Longest Increasing Subsequence

### [Problem link](https://leetcode.com/problems/number-of-longest-increasing-subsequence/)

###### tags: `leedcode` `python` `c++` `medium` `DP`

Given an integer array<code>nums</code>, return the number of longest increasing subsequences.

**Notice** that the sequence has to be **strictly** increasing.

**Example 1:**

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

**Example 2:**

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

**Constraints:**

- <code>1 <= nums.length <= 2000</code>
- <code>-10⁶ <= nums[i] <= 10⁶</code>

## Solution 1 - DP
#### Python

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        
        dp = [1] * n  # dp[i]: 以nums[i]為結尾的LIS長度
        cnt = [1] * n  # cnt[i]: 以nums[i]為結尾的LIS數量

        max_cnt = 0
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j] + 1 > dp[i]:
                        cnt[i] = cnt[j]
                        dp[i] = dp[j] + 1
                    elif dp[j] + 1 == dp[i]:
                        cnt[i] += cnt[j]

            max_cnt = max(max_cnt, dp[i])

        res = 0
        for i in range(n):
            if dp[i] == max_cnt:
                res += cnt[i]

        return res

#### C++

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        int maxLen = 0;
        int res = 0;
        vector<int> dp(n, 1);
        vector<int> cnt(n, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] >= dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                res = cnt[i];
            } else if (dp[i] == maxLen) {
                res += cnt[i];
            }
        }
        return res;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O(n) |

## Note
sol1:
dp = [1] * n # dp[i]: 以nums[i]為結尾的LIS長度
cnt = [1] * n # cnt[i]: 以nums[i]為結尾的LIS數量

這段code是核心, 理解這段code很重要
if dp[j] + 1 > dp[i]:
    cnt[i] = cnt[j]
    dp[i] = dp[j] + 1
elif dp[j] + 1 == dp[i]:
    cnt[i] += cnt[j]

[Leetcode官方題解](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/solutions/1007075/zui-chang-di-zeng-zi-xu-lie-de-ge-shu-by-w12f/)
[代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0673.%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97%E7%9A%84%E4%B8%AA%E6%95%B0.md)