動機

dp的比較好理解

Problem

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

 

Example 1:

Input: nums = [1,3,5,4,7]Output: 2Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]Output: 5Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

 

Constraints:

  • 1 <= nums.length <= 2000
  • -106 <= nums[i] <= 106

Sol

在dp時留一個紀錄總數的位置

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        @cache
        def dp(i):
            if i == 0:
                return [1,1] # len, cnt
            else:
                ls = [dp(x) for x in range(i) if nums[x] < nums[i]]
                l = max(ls,key=itemgetter(0),default=[0])[0]
                cnt = max(1,sum([x[1] for x in ls if x[0] == l], 0))
                return [l+1, cnt]
        dps = [dp(i) for i in range(len(nums))]
        maxlen = max(dps,key=itemgetter(0))[0]
        #print(dps)
        return sum([x[1] for x in dps if x[0] == maxlen])

Case Study

另外有一個patience sort的作法，這裡，之後有時間來研究