步步高升 最長遞增子序列 Longest Increasing Subsequence_DP_Leetcode #300

Denys Sudilkovsky on Unsplash

題目敘述 Longest Increasing Subsequence

給定一個輸入陣列nums，要求我們計算出最長遞增子序列的長度是多少？

註:

子序列 不要求連續，可以把題目想成是找出一組遞增數列，而且數列長度是最長的。

測試範例

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

2 -> 3 -> 7 -> 101
2 -> 3 -> 7 -> 18
2 -> 5 -> 7 -> 101
2 -> 5 -> 7 -> 18
上述四條皆為最長遞增子序列，長度=4​

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

0 -> 1 -> 2 -> 3
最長遞增子序列長度 = 4​

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

大家都一樣，沒辦法造出更長的數列了。
最長遞增子序列長度 = 1​

約束條件

Constraints:

• 1 <= nums.length <= 2500

輸入陣列長度介於1~2500之間。

• -10^4 <= nums[i] <= 10^4

每個陣列元素介於 負一萬~正一萬 之間。

本題的教學影片

觀察

題目說要找最長遞增子序列，相當於找最長的遞增數列。

假如我現在當下在index i，擁有的數字是nums[i]

可以回頭看，往左邊看那些比較小的index，
看看有沒有比我(nums[i])還小的數字num[k] ?

假如有的話，就可以試著從前面延伸過來，並且更新遞增子序列的長度。

每個index i 都可以依循同樣的邏輯做檢查和更新。

演算法 DP動態規劃 + 回頭看的技巧

怎麼定義DP狀態?

承接剛剛觀察點的思考，可以定義DP[i] = 以 index i 為終點的遞增子序列長度。

怎麼推導DP狀態轉移關係式?

假如左手邊有比較小的數字可以延伸過來，那就可以試著延伸、更新遞增子序列的長度。

DP[i] = max( DP[i], DP[k] + 1) 如果存在某個 k < i 且 nums[k] < nums[i]

初始條件(終止條件)為何?

最差情況下，就是左手邊的數字都比自己大，或者 和自己相等。
這時候，遞增子序列只有自己，遞增子序列的長度=1

DP[i] = 1

OK，到這邊，DP狀態定義、狀態轉移關係式、初始條件都具備了！

轉成對應的程式碼即可。

程式碼 DP動態規劃 + 回頭看的技巧

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:    
        
        size = len(nums)
        
        # default value is 1, because each array element itself can be smallest LIS with length = 1
        len_LIS = [1 for _ in range(size)]
        
        # for each subsequence ending at index i
        for i in range(size):
            
            # for each prefix subsequence ending at k
            for k in range(i):
            
                if nums[k] < nums[i]:
                    
                    # check if we can extend LIS length from prefix subsequence
                    len_LIS[i] = max(len_LIS[i], len_LIS[k]+1)
                    
        
        return max(len_LIS)

複雜度分析

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

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

空間複雜度: O(n)

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

關鍵知識點

使用到數列題實用的"回頭看"的技巧，回頭找符合條件的元素。
在這題，就是回頭看，找比較小的元素。

Reference

[1] Longest Increasing Subsequence - LeetCode

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