673. Number of Longest Increasing Subsequence

link

Method 1 Backtrack

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:

        n = len(nums)
        
        @cache
        def backtrack(s):
            if s == n:
                return 0

            res = 1

            for i in range(s+1, n):
                if nums[i] > nums[s]:
                    res = max(res, 1+backtrack(i))

            return res

        @cache
        def backtrack2(s, current):
            if current + 1 == lng:
                # print(s, current)
                return 1
            if n - s + current < lng :
                # print(s, current)
                return 0

            res = 0

            for i in range(s+1, n):
                if nums[i] > nums[s]:
                    res += backtrack2(i, current+1)

            return res

        lng = 0

        for i in range(len(nums)):
            lng = max(lng, backtrack(i))
        
        res = 0
        for i in range(len(nums)):
            res += backtrack2(i, 0)

        return res

Method 2 DP

# dp[i] number of longest increasing subsequences at nums[0:i].

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:

        n = len(nums)
        
        if n == 1:
            return 1
        
        dp_LIS = [1] * n
        dp_count = [1] * n
        
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp_LIS[j] == dp_LIS[i]:
                        dp_LIS[i] += 1
                        dp_count[i] = dp_count[j]
                    elif dp_LIS[j] + 1 == dp_LIS[i]:
                        dp_count[i] += dp_count[j]
        
        maxLen = max(dp_LIS)
        
        return sum([dp_count[i] for i in range(n) if dp_LIS[i] == maxLen])