673. Number of Longest Increasing Subsequence (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        dp = [[1, 1] for _ in range(len(nums))]
        result = [0, 0]
        for i, num in enumerate(nums):
            for j in range(i - 1, -1, -1):
                if nums[i] > nums[j]:
                    if dp[j][0] == dp[i][0] - 1:
                        dp[i][1] += dp[j][1]
                    elif dp[j][0] > dp[i][0] - 1:
                        dp[i] = [dp[j][0] + 1, dp[j][1]]
            if dp[i][0] > result[0]:
                result[ : ] = dp[i]
            elif dp[i][0] == result[0]:
                result[1] += dp[i][1]
        return result[1]