動態規劃（一）

動態規劃開胃菜

動態規劃中有幾個重要概念，分別是

• 狀態轉移方程
• 重疊子問題

遞推與動態規劃

先來做一道高中數學題

通俗來講動態規劃 演演算法並不直接給出最終結果的求解表示式，而是通過找到問題規模之間的 動態轉移方程，藉此不斷縮小問題規模，逐漸迫近base case

解法一

def func(n):
    if n == 0:
        return 2
    return func(n - 1) + 3

自頂向下的計算順序，正如上圖紫線箭頭方向

解法二

def func2(n):
    # 確定dp[i] 的含義
    # d[i] == func(i)
    # dp陣列規模,規模與dp[i]的定義密切相關
    # 根據dp[i] 定義，func2(n) 對應dp[n]
    # 要使得dp[n] 合法，陣列長度要為 n+1
    dp = [0] * (n + 1)
    # base_case
    dp[0] = 2
    # dp陣列的遍歷順序
    # func(i) = func(i-1) + 3
    # dp[i] = dp[i-1] + 3
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 3
    return dp[n]

自底向上解法，正如上圖綠色箭頭方向

重疊子問題

直觀瞭解了狀態轉移方程後，接著來以斐波那契額數列問題為例看重疊子問題。

$ F(0)=0, \quad F(1)=1,\quad F(n)=F(n-1)+F(n-2) \quad\left(n \geq 2, \quad n \in N^{*}\right) $

解法一

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

不難發現， fib(18) 被執行了兩次，fib(17) 被執行了3次。fib(16) 被執行了4次。。。

計算過的問題我們不想重複計算，需要一個備忘錄記錄我們算過的fib(n)。

解法一 + 備忘錄

# 使用一個字典儲存計算過得fib(n)
# n為鍵，fib(n) 為值
memo = {}

def fib1(n):
    # 如果備忘錄中有記載，直接返回
    if n in memo.keys():
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    val = fib(n - 1) + fib(n - 2)
    memo[n] = val
    return val

備忘錄相當於為整個遞迴遍歷樹進行了一個剪枝操作。

fib(18) 被執行了1次，fib(17) 被執行了1次。fib(16) 被執行了1次。。。

解法二

def fib2(n):
    # 確定dp[i]的含義
    # dp[i] = fib(i)
    # dp陣列規模
    dp = [0] * (n + 1)
    # base_case
    dp[0] = 0
    dp[1] = 1
    # dp 陣列遍歷方向
    # fib(i) = fib(i-1) + fib(i-2)
    # dp[i] = dp[i-1] + dp[i-2]
    # dp[大] 依賴 dp[小]  所以先算dp[小]
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

使用dp陣列自頂向下來解不存在 重疊子問題。

空間開銷為 O(n)，不難看出，每次計算新值只依賴前面兩個值。因此我們可以使用兩個變數來記錄，而不使用dp陣列。

解法二 + 狀態壓縮

def fib3(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return re1
    # prev初始為dp[1]
    prev = 1
    # curr初始為dp[2]
    curr = 1
    # 注意迭代次數
    # 注意i = 3時，迭代了1輪，迭代結束 curr == dp[3]
    # 注意i = 4時，迭代了2輪，迭代結束 curr == dp[4]
    # 所以 i = n 時，迭代結束時 curr == dp[n]
    # range 前閉後開 so ...
    for i in range(3, n + 1):
        sum = prev + curr
        prev = curr
        curr = sum
    return curr

總結一下，當出現重疊子問題時，自定向下的解法一需要備忘錄來剪枝，自底向上的解法二需要狀態壓縮減少空間開銷。

一般來說，自頂向下的方法如果不用備忘錄剪枝，一般會超時。自底向上的方法不進行狀態壓縮一般也沒事。