化簡無所不在 用LIS的DP模型解Num of Longest Increasing Subseq._LC#673

Nikola Murniece on Unsplash

題目敘述 Number of Longest Increasing Subsequence

給定一個輸入陣列nums，要求我們計算出最長遞增子序列總共有幾條？

註:

子序列 不要求連續。

測試範例

Example 1:

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

最長的遞增子序列長度為4
總共有兩條，分別是
[1,3,4,7]
[1,3,5,7]​

Example 2:

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

最長的遞增子序列長度為1
總共有五條，分別是
[2​]
[2​]
[2​]
[2​]
[2​]

本題的教學影片

觀察　

其實這題和Longest Common Subsequence 幾乎一樣，只是改成問 最長遞增子序列有幾條。

(也就是說，找到最長遞增子序列的長度後，計算總共有幾條遞增子序列是最長的。)

本來，我們在Longest Common Subsequence的演算法就會記錄遞增子序列的長度，
現在只要多紀錄一個counting的計數器，負責記錄有幾條。

最後，把長度最長的遞增子序列數量作加總，就是最終答案。

演算法
化簡到Longest Common Subsequence 的DP模型

定義length[i] 代表以index i為結尾的遞增子序列最大長度。

定義count[i] 代表以index i為結尾的最長遞增子序列的數量。

假如長度延伸後比原本的大，那麼長度累加1，方法數從延伸的地方搬過來。

if (length[k] + 1) > length[i]:

	# nums[k] make it longer to increasing subsequence ending in nums[i]
  length[i], count[i] = length[k]+1, count[k]

假如長度延伸後和原本等長，那麼長度不用更新(因為等長)，方法數從延伸的地方累加。

elif (length[k] + 1) == length[i]:
	
	# nums[k] add some new paths of increasing subsequence ending in nums[i]
	count[i] += count[k]

程式碼
化簡到Longest Common Subsequence 的DP模型

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

        if not nums:
            # Quick response for empty list
            return 0
        
        n = len(nums)
        
        # record of length of increasing subsequence
        length = [1 for _ in range(n)]
        
        # record the path count of increasing subsequence
        count = [1 for _ in range(n)]
            
        # scan each number, where increasing subsequence ending in nums[i]
        for i in range(n):
            
            # for every number before nums[i]
            for k in range(i):

                if nums[k] < nums[i]:
                    # nums[k] can add to increasing subsequence ending in nums[i]
                    
                    if (length[k] + 1) > length[i]:
                        # nums[k] make it longer to increasing subsequence ending in nums[i]
                        length[i], count[i] = length[k]+1, count[k]
                
                    elif (length[k] + 1) == length[i]:
                        # nums[k] add some new paths of increasing subsequence ending in nums[i]
                        count[i] += count[k]
       
				# get the length of lonest increasing subsequence
        max_length = max(length)
        
        # report total path count of longest increasing subsequence
        return sum( cur_count for cur_len, cur_count in zip(length, count) if cur_len == max_length )

複雜度分析

時間複雜度:O(n^2)

雙層迴圈，外層迭代index i，內層迭代index k，O(n) * O(n) = O(n^2)

空間複雜度: O(n)

DP table length, count 所需空間大小為O(n)線性級別。

關鍵知識點

使用到數列題實用的"回頭看"的技巧，回頭找符合條件的元素。

在這題，就是回頭看，找比較小的元素去延伸遞增子序列的長度，並且記錄有幾條。

Reference

[1] Number of Longest Increasing Subsequence - LeetCode

回到DP特訓班目錄 和 學習路徑