673. Number of Longest Increasing Subsequence - Explanation

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

        def dfs(i, length):
            nonlocal LIS, res
            if LIS < length:
                LIS = length
                res = 1
            elif LIS == length:
                res += 1

            for j in range(i + 1, len(nums)):
                if nums[j] <= nums[i]:
                    continue
                dfs(j, length + 1)

        for i in range(len(nums)):
            dfs(i, 1)
        return res

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

        def dfs(i):
            if i in dp:
                return

            maxLen = maxCnt = 1
            for j in range(i + 1, len(nums)):
                if nums[j] > nums[i]:
                    dfs(j)
                    length, count = dp[j]
                    if 1 + length > maxLen:
                        maxLen = length + 1
                        maxCnt = count
                    elif 1 + length == maxLen:
                        maxCnt += count
            dp[i] = (maxLen, maxCnt)

        lenLIS = res = 0
        for i in range(len(nums)):
            dfs(i)
            maxLen, maxCnt = dp[i]
            if maxLen > lenLIS:
                lenLIS = maxLen
                res = maxCnt
            elif maxLen == lenLIS:
                res += maxCnt

        return res

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0, 0] for _ in range(n)]
        lenLIS, res = 0, 0

        for i in range(n - 1, -1, -1):
            maxLen, maxCnt = 1, 1
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    length, count = dp[j]
                    if length + 1 > maxLen:
                        maxLen, maxCnt = length + 1, count
                    elif length + 1 == maxLen:
                        maxCnt += count

            if maxLen > lenLIS:
                lenLIS, res = maxLen, maxCnt
            elif maxLen == lenLIS:
                res += maxCnt
            dp[i] = [maxLen, maxCnt]

        return res

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[[0, 0], [nums[0], 1]]]

        def bs1(num):
            l, r = 0, len(dp) - 1
            j = len(dp) - 1
            while l <= r:
                mid = (l + r) // 2
                if dp[mid][-1][0] < num:
                    l = mid + 1
                else:
                    j = mid
                    r = mid - 1
            return j

        def bs2(i, num):
            if i < 0:
                return 1
            l, r = 1, len(dp[i]) - 1
            j = 0
            while l <= r:
                mid = (l + r) // 2
                if dp[i][mid][0] >= num:
                    j = mid
                    l = mid + 1
                else:
                    r = mid - 1
            return dp[i][-1][1] - dp[i][j][1]

        LIS = 1
        for i in range(1, n):
            num = nums[i]
            if num > dp[-1][-1][0]:
                count = bs2(LIS - 1, num)
                dp.append([[0, 0], [num, count]])
                LIS += 1
            else:
                j = bs1(num)
                count = bs2(j - 1, num)
                dp[j].append([num, dp[j][-1][1] + count])

        return dp[-1][-1][1]