673.md

673. Number of Longest Increasing Subsequence

Solution 1 (time O(n^2), space O(n))

# Dynamic programming
class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        dp = [0 for _ in range(len(nums))]
        cnt = [0 for _ in range(len(nums))]
        dp[0] = 1
        cnt[0] = 1
        for i in range(1, n):
            dp[i] = 1
            cnt[i] = 1
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        cnt[i] = cnt[j]
                    elif dp[j] + 1 == dp[i]:
                        cnt[i] += cnt[j]
        ans = 0
        max_dp = max(dp)
        for i in range(n):
            if dp[i] == max_dp:
                ans += cnt[i]
        return ans