# 0673. Number of Longest Increasing Subsequence
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/number-of-longest-increasing-subsequence/
## 思路
和[0300. Longest Increasing Subsequence](https://hackmd.io/oPc5yL1oRhGtGP8UdRd3_g)类似
但需要用另外一个cnt array记录以nums[i]结尾的longest increasing subsequence的长度
## Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int maxLen = 0;
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(cnt, 1);
        int ans = 0;
        
        for(int i=0; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i]>nums[j]){
                    if(dp[j]+1==dp[i]) cnt[i] += cnt[j];
                    else if(dp[i]<dp[j]+1){
                        dp[i] = dp[j]+1;
                        cnt[i] = cnt[j];
                    }  
                } 
            }
            if(maxLen == dp[i]) ans += cnt[i];
            if(maxLen < dp[i]){
                ans = cnt[i];
                maxLen = dp[i];
            }
        }
        return ans;
    }
}