[DP] LeetCode 673. Number of Longest Increasing Subsequence

Solution O(n^2)

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

        dp = [1] * n
        count = [1] * n

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

            if dp[i] > max_length:
                max_length = dp[i]
                ans = count[i]
            elif dp[i] == max_length:
                ans += count[i]

        return ans

This problem is similar to the problem longest increasing subsequence. The only difference is that we need to create a count array to count the number of the longest increasing subsequence. Dynamic programming is all about sub-problems. It is important to come up with a solution using the sub-problems.

1. If the length of subsequence increases, we set count[i] = count[j]. This is because we need to use the number of subsequence for the previous length, in order to update it for the longer current length.
2. If the length of the subsequence does not increase, this means that there is another subsequence available. Hence, use count[i] += count[j].
3. Then, we need to update the value of answer.

Here is an example of a table showing the whole process.

	1	2	4	3	5	4	7	2
dp	1	2	3	3	4	4	5	2
count	1	1	1	1	2	1	3	1