leetcode(力扣) 673. 最長遞增子序列的個數 (動态規劃)

題目在這:​​https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/​​

思路分析:

這道題是第 300題的進階版，具體的思路大家可以看一下我另一篇文章，裡面有關于300題的詳解，​​300. 最長遞增子序列​​

第300題求最長的遞增子序列，而這個題要求最長的個數。

比如 ​​

​[1,3,5,4,7]​

​​ 如果在第300題中，顯然最長的遞增子序列是​

​[1,3,5,7]​

​​ 或者​

​[1,3,4,7]​

​ 無論是那個 長度都是4。是以300題可以直接輸出4即可。

而在本題中，上面兩種情況都是4，是以有兩個最長的遞增子序列，輸出2.

基于300題的思路，我們建立dp數組和一個count計數數組。

• dp [i] 表示到i時的最長遞增子序列長度
• count [i] 表示到i是最長遞增子序列的個數

周遊，當nums[i] > nums[j] 時。

我們判斷dp[i] 是否小于dp[j] + 1，如果小于，則說明發現了更長的遞增子序列，此時更新dp[i] ，計數數組count[i]不變。

但還有一個相等的情況 ，即 dp[i] == dp[j] +1，此時說明發現了相同長度的最長子序列。則 讓計數數組相加。

找到最長的長度，然後周遊整個dp數組，看看dp中長度為最長長度的位置所對應的計數數組中該位置有幾個，求和即可。

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        dp = len(nums) * [1]
        count = len(nums) * [1]
        max_length = float('-inf')
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[i] < dp[j] + 1:
                        # 更新目前dp所記錄的最長子序列長度
                        dp[i] =  dp[j] + 1
                        count[i] = count[j]
                        # 直接繼承前面所記錄的最長子序列長度個數
                        # 這裡是可以直接繼承的，不是相加，想清楚，因為dp[i] < dp[j] +1
                        # 既已經發現了新的大的數，是以最長長度已經更新，到前面那個數有幾個最長個數，到目前這個數就有幾個，想清楚。
                    elif dp[i] == dp[j] + 1:
                        count[i] +=count[j]
                        # 發現了相等的情況，顯然，這裡是相加的關系。
            max_length = max(dp)  # 找到最長的長度
        res = 0
        print(dp)
        print(count)
        for k in range(len(nums)):
            if dp[k] == max_length:
                res +=count[k]
        return