動態規劃（二）最長遞增子序列

• 2022 年 10 月 19 日
• 筆記
• 動態規劃, 演算法

最長遞增子序列

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

子序列 是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其餘元素的順序。例如，[3, 6, 2, 7] 是數組 [0, 3, 1, 6, 2, 2, 7] 的子序列。注意 子序列 和 子串 的區別，子串一定是連續的，而子序列不一定是連續的。

示例 1：

輸入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
輸出：4
解釋：最長遞增子序列是 [2, 3, 7, 101]，因此長度為 4 。

示例 2：

輸入：nums = [0, 1, 0, 3, 2, 3]
輸出：4

示例 3：

輸入：nums = [7, 7, 7, 7, 7, 7, 7]
輸出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

進階：

你能將演算法的時間複雜度降低到 O(n log(n)) 嗎?

來源：力扣（LeetCode）
鏈接：//leetcode.cn/problems/longest-increasing-subsequence

tips:

動態規劃題目的核心就是找出大規模與小規模之間的關係。

拿示例1來說，A = [10, 9, 2, 5, 3, 7, 101, 18]

比 A 規模更小的是B = [10, 9, 2, 5, 3, 7, 101] ，若知道 B 中的最長遞增子序列的長度 4 後能否在此基礎上快速推斷出A的最長子序列？顯然不能。因為我們不知道 A比 B 多出的尾部元素 18是否可以加到某個現有最長子序列的尾部，形成更長的子序列。

不管是自頂向下的函數遞歸法，還是自底向上的數組法（也叫dp數組法，動態規劃 dynamic programming，簡稱dp），我們最最開始應該做的就是明確 函數（返回值）含義 或 dp數組中下標i與值dp[i]的含義。

我們通常可以在定義中添加一些限制條件，便於我們找出不同規模之間的遞推關係（動態轉移方程）。

對比這兩種定義：

嘗試尋找遞推關係

nums = [10, 9, 2, 5, 3, 7, 101, 18]

不加限制：

這個過程中，dp[大] 的計算不能依賴已知的dp[小]。不能依賴即不能遞推，所以這是糟糕的定義🥴

添加限制：

能否利用dp[小] 推斷 dp[大] ❓

若nums[i] 比 nums[x] 大，nums[i] 就可以加到以nums[x]為結尾的最長遞增序列後面。以nums[i]結尾的遞增子序列長度比以nums[x]結尾的遞增子序列長1

if nums[i] > nums[比i小]：
	dp[i] = dp[比i小] + 1

nums[4] = 3 ，比 nums[2] = 2 大。所以3可以加到以2為結尾的遞增序列 [2] 中，形成新的遞增子序列 [2, 3]。 dp[4] = dp[2] + 1 = 2

若nums[i] 大於多個nums[比i小]，dp[i] = max(dp[比i小]+1，dp[比i小]+1)

差不多可以可程式碼了。

程式碼

自底向上 dp數組法

nums = [10, 9, 2, 5, 3, 7, 101, 18]
# dp數組
# 定義dp數組下標含義
# dp[i], 以nums[i]這個數結尾的最長遞增子序列的長度
# 定義決定了數組大小
# base case
dp = [1] * (len(nums))

# dp[大] 依賴dp[小] 先計算di[小]
for i in range(1, len(nums)):
    for j in range(0, i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j] + 1)

自頂向下 函數遞歸法

# 最長遞增子序列
nums = [10, 9, 2, 5, 3, 7, 101, 18]

# 自頂向下添加備忘錄
# base case 已在備忘錄中
memo = {0: 1}
def func(n):
    # func(i) 代表以nums[i]這個數結尾的最長遞增子序列的長度
    # func(2) 代表以nums[2]這個數結尾的最長遞增子序列(2)的長度
    # func(4) 代表以nums[4]這個數結尾的最長遞增子序列(2,3)的長度
    if n in memo.keys():
        return memo[n]
    # 查看調用次數,驗證備忘錄功效
    print("函數調用func(", n, ")")
    max_length = 1
    for i in range(n - 1, -1, -1):
        val = func(i)
        if nums[n] > nums[i]:
            max_length = max(max_length, val + 1)
    memo[n] = max_length
    return max_length

無備忘錄，用於對比的綠葉

# 最長遞增子序列
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# 自定向下解法
def func(n):
    # func(i) 代表以nums[i]這個數結尾的最長遞增子序列的長度
    # func(2) 代表以nums[2]這個數結尾的最長遞增子序列(2)的長度
    # func(4) 代表以nums[4]這個數結尾的最長遞增子序列(2,3)的長度
    # 查看調用次數
    print("函數調用func(", n, ")")
    if n == 0:
        return 1
    max_length = 1
    for i in range(n - 1, -1, -1):
        val = func(i)
        if nums[n] > nums[i]:
            max_length = max(max_length, val + 1)
    return max_length