動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法

• 動態(tài)規(guī)劃問題的一般形式就是求最值:
  • 動態(tài)規(guī)劃是運籌學(xué)的一種最優(yōu)化方法
• 動態(tài)規(guī)劃的應(yīng)用場景:
  • 求最長遞增子序列
  • 求最小編輯距離
• 動態(tài)規(guī)劃的核心問題:
  • 窮舉
  • 因為要求最值,肯定要將所有可行的答案窮舉出來,然后在其中找最值
• 動態(tài)規(guī)劃的窮舉很特殊:
  • 存在重疊子問題:
    • 如果暴力窮舉效率低下
    • 需要使用備忘錄或者DP Table來優(yōu)化窮舉過程,避免不必要的計算
  • 具備最優(yōu)子結(jié)構(gòu): 這樣才能通過子問題的最值找到原問題的最值
  • 列出正確的狀態(tài)轉(zhuǎn)移方程才能正確地窮舉: 因為窮舉出所有可行解并不是一件容易的事
• 動態(tài)規(guī)劃三要素:
  • 重疊子問題
  • 最優(yōu)子結(jié)構(gòu)
  • 狀態(tài)轉(zhuǎn)移方程
• 狀態(tài)轉(zhuǎn)移方程思維框架:
  • 明確狀態(tài)
  • 定義DP數(shù)組或者函數(shù)的含義
  • 明確選擇
  • 明確base case

斐波那契數(shù)列

直接遞歸

• 斐波那契數(shù)列數(shù)列的數(shù)學(xué)形式就是遞歸的,代碼如下:

int fib(int N) {
    if (N == 1 || N == 2) {
        return 1;
    } 
    return fib(N-1) + fib(N-2);
}

這是最簡單易懂的直接遞歸的方法,同時也是效率最低的方法,可以通過畫出遞歸樹看出

• 遞歸的問題分析,最好都畫出遞歸樹,方便分析算法的復(fù)雜度,尋找算法低效的原因
• 遞歸算法的時間復(fù)雜度 = 子問題個數(shù) * 解決一個子問題需要的時間

• 當(dāng)N=20時,斐波那契數(shù)列遞歸樹分析:
  • 要計算f(20),就要計算出f(19)和f(18),然后要計算f(19),就要計算出f(18)和f(17),以此類推.最后到f(2)和f(1)的時候,結(jié)果已知.此時遞歸樹結(jié)束
  • 根據(jù)遞歸算法時間復(fù)雜度等于子問題個數(shù)乘以解決一個子問題需要的時間:
    • 子問題個數(shù): 也就是遞歸樹中節(jié)點的總數(shù).因為二叉樹的節(jié)點總數(shù)為指數(shù)級別,所有子問題的個數(shù)為O(2^N)
    • 解決一個子問題需要的時間: 因為這個算法中沒有循環(huán),只有f(n-1)+f(n-2)一個加法操作,所有時間為O(1)
    • 直接遞歸算法時間復(fù)雜度: O(2ⁿ),為指數(shù)級別.相當(dāng)復(fù)雜
  • 觀察遞歸樹,分析出算法低效的原因:
    • 存在大量的重復(fù)計算
    • f(18)被計算了兩次,以f(18)為根的遞歸樹體量巨大,多算一遍,就會耗費大量時間
    • 而且,不止f(18)這一個節(jié)點會被重復(fù)計算,進而導(dǎo)致算法低下
    • 這個問題就是動態(tài)規(guī)劃的第一個性質(zhì) : 重疊子問題

帶備忘錄的遞歸算法

• 重疊子問題解決:
  • 因為耗時的原因是因為重復(fù)計算
  • 那么可以創(chuàng)建一個備忘錄:
    • 每次算出某個子問題的答案先記錄到備忘錄中再返回
    • 每次遇到一個子問題先去備忘錄中查詢
    • 如果發(fā)現(xiàn)備忘錄中已經(jīng)存在這個解決過的問題,直接獲取答案,不需要再耗時計算了
• 通常使用數(shù)組作為備忘錄, 也可以使用Hash表作為備忘錄:

int fib(int N) {
    if (N < 1) {
        return 0;
    }
    // 備忘錄初始化為0 
    vector<int> memo(N+1, 0);
    // 初始化最簡情況
    return helper(memo, N); 
}

int helper(vector<int>& memo, int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 已經(jīng)計算過的直接返回
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

• 帶備忘錄的遞歸算法的遞歸樹分析:
  • 帶備忘錄的遞歸樹算法是將一棵存在巨量冗余的遞歸樹通過剪枝, 改造成了一幅不存在冗余的遞歸圖,極大減少了子問題,即遞歸樹中節(jié)點的個數(shù)
  • 根據(jù)遞歸算法時間復(fù)雜度等于子問題個數(shù)乘以解決一個子問題需要的時間:
    • 子問題個數(shù): 即遞歸樹中節(jié)點的總數(shù).由于不存在冗余計算,子問題就是f(1),f(2)...f(20),數(shù)量和輸入的規(guī)模n成正比,所以子問題的個數(shù)就是O(n)
    • 解決一個子問題需要的時間: 因為這個算法中沒有沒有循環(huán),只有加法操作,所以時間為O(1)
    • 帶備忘錄的遞歸算法時間復(fù)雜度: O(n).比直接遞歸算法高效得多

• 帶備忘錄的遞歸解法的效率和迭代的動態(tài)規(guī)劃解法一樣:
  • 帶備忘錄的遞歸解法: 自頂向下
    • 從上向下延伸
    • 從一個規(guī)模較大的源問題,向下逐漸分解問題規(guī)模,直到觸底.然后逐層返回答案
  • 迭代的動態(tài)規(guī)劃解法: 自底向上
    • 直接從問題規(guī)模最小的最底層開始往上推,直到推導(dǎo)出需要的答案.這就是動態(tài)規(guī)劃的思路
    • 動態(tài)規(guī)劃一般都脫離了遞歸,去采用循環(huán)迭代完成計算

DP數(shù)組的迭代算法

• 在備忘錄的基礎(chǔ)上,將備忘錄獨立出來成為一張表,叫作DP Table
• 在DP Table上完成自底向上的推算:

int fib(int N) {
    vector<int> dp(N+1, 0);
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

DP Table和備忘錄的遞歸樹剪枝后的結(jié)構(gòu)很相似,只不過是反過來計算而已.實際上,帶備忘錄的遞歸解法中的備忘錄, 最終完成的就是這個DP Table. 所以帶備忘錄的遞歸算法和DP數(shù)組的迭代算法在大部分情況下的算法效率是相同的

• 狀態(tài)轉(zhuǎn)移方程: 一種描述問題結(jié)構(gòu)的數(shù)學(xué)形式
  • 狀態(tài)轉(zhuǎn)移: 比如想要將f(n)做成一個狀態(tài)n,這個狀態(tài)n是由狀態(tài)n-1和狀態(tài)n-2相加轉(zhuǎn)移而來
  • 狀態(tài)轉(zhuǎn)義方程是解決問題的核心
  • 狀態(tài)轉(zhuǎn)移方程直接代表著暴力解法
• 動態(tài)規(guī)劃最困難的就是寫出狀態(tài)轉(zhuǎn)移方程

斐波那契數(shù)列解法補充

• 根據(jù)斐波那契數(shù)列的狀態(tài)轉(zhuǎn)移方程:
  • 當(dāng)前狀態(tài)只和之前的兩個狀態(tài)有關(guān)
  • 所以并不需要一個很長的DP Table來存儲所有狀態(tài)
  • 只要存儲之間的兩個狀態(tài)就可以
  • 可以將空間復(fù)雜度優(yōu)化為O(1)

int fib(int n) {
    if (n == 1 || n ==2) {
        return 1;
    }
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

湊零錢問題

• 題目:
  • 給k種面值的硬幣,硬幣面值分別為c1, c2,...ck. 每種硬幣的數(shù)量無限,需要湊夠總金額amount. 最少需要幾枚硬幣湊出這個金額,如果不能湊出則返回 -1
• 對于計算機來說,解決這個問題的方法就是將所有可能的湊硬幣方法都窮舉出來,然后找找看最少需要多少枚硬幣

直接遞歸

• 要符合最優(yōu)子結(jié)構(gòu),子問題之間必須互相獨立
• 湊零錢問題分析:
  • 這個問題是動態(tài)規(guī)劃問題,因為具有最優(yōu)子結(jié)構(gòu)
    • 原問題: 比如想要求amount=11時的最少硬幣數(shù)
    • 子問題: 如果知道湊出amount=10的最少硬幣數(shù)
    • 只需要將子問題的答案加1. 再選一枚面值為1的硬幣后就是原問題的答案
    • 因為硬幣的數(shù)量是沒有限制的,子問題之間沒有限制,是相互獨立的
• 確定是動態(tài)規(guī)劃問題后,就要思考如何列出狀態(tài)轉(zhuǎn)移方程:
  • 先確定狀態(tài):
    • 狀態(tài)就是原問題和子問題中變化的數(shù)量
    • 由于硬幣數(shù)量是無限的,所以唯一的狀態(tài)就是目標(biāo)金額amount
  • 然后確定DP函數(shù)的定義:
    • 當(dāng)前的目標(biāo)金額是n,至少需要dp(n)個硬幣湊出該金額
  • 然后確定選擇并擇優(yōu):
    • 也就是對于每個狀態(tài),可以做出什么選擇改變當(dāng)前狀態(tài)
    • 無論當(dāng)前的目標(biāo)金額是多少,選擇就是從面額列表coins中選出一個硬幣,然后目標(biāo)金額就會減少
    • 偽碼如下:

       def coinChange(coins: List[int], amount: int):
        # 定義: 要湊出金額n,至少需要dp(n)個硬幣
        def dep(n):
            # 做選擇: 選擇需要硬幣最少的那個結(jié)果
            for coin in coins:
                res = min(res, 1 + dp(n - coin))
            return res;
        # 計算出要求的問題dp(amount)
        return dp(amount)
      

  • 最后明確base case:
    • 明確初始的已知狀態(tài)
    • 目標(biāo)金額為0時,所需硬幣數(shù)量為0.當(dāng)目標(biāo)金額小于0時,無解.返回-1

def coinChange(coins: List[int], amount: int):
    def dp(n):
        if n==0: return 0
        if n < 0: return -1
        # 求最小值,所以初始化為正無窮
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coins)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1
    return dp(amount);

• 以上代碼的數(shù)學(xué)形式就是通過直接遞歸獲取到的狀態(tài)轉(zhuǎn)移方程
• 消除重疊子問題:
  • 直接遞歸算法的遞歸樹分析:
    • 根據(jù)時間復(fù)雜度等于子問題總數(shù)乘以每個子問題的時間:
      • 子問題總數(shù): 這個問題的子問題具體個數(shù)比較難看出,可以分析為O(n^k),為指數(shù)級別的個數(shù)
      • 每個子問題的時間: 每個子問題含有一個for循環(huán),所以時間復(fù)雜度為O(k)
      • 算法時間復(fù)雜度: O(k * n^k).是指數(shù)級別

帶備忘錄的遞歸算法

• 可以通過備忘錄消除重疊子問題:

def coinChanges(coins: List[int], amount: int):
    # 備忘錄
    memo = dict()
    def dp(n):
        # 查看備忘錄,避免重復(fù)計算
        if n in memo: return memo[n]
        # 如果備忘錄中不存在,則進行計算
        if n = 0: return 0
        if n < 0: return -1
        # 求最小值,所以初始化為正無窮
        res = float('INF')
        for coin in coins:
            subproblem = dep(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        # 將計算結(jié)果記入備忘錄
        memo[n] = res if res != float('INF') else -1
        return memo[n]
    return dep(amount) 

• 帶備忘錄的遞歸算法的遞歸樹分析:
  • 根據(jù)算法時間復(fù)雜度等于子問題總數(shù)乘以每個子問題的時間
    • 子問題總數(shù): 由于引用了備忘錄,大大減少了子問題數(shù)目,完全消除了子問題的冗余,所以子問題的總數(shù)不會超過n,即子問題的數(shù)目為O(n)
    • 每個子問題的時間: 由于存在for循環(huán),每個子問題的處理時間為O(k)
    • 算法時間復(fù)雜度: O(kn).大大提高了算法效率

DP數(shù)組的迭代算法

• 自底向上使用DP Table來消除重疊子問題

int coinChanges(vector<int> coins, int amount) {
    // 數(shù)組大小為amount+1,初始值也為amount+1
    vector<int> dp(amount + 1, amount + 1);
    /*
     * dp[i] = x:
     *  當(dāng)目標(biāo)金額為i時,至少需要x枚硬幣   
     */
     for (int i = 0; i < dp.size(); i++) {
        // 內(nèi)層for求所有子問題+1的最小值
        for (coin in coin) {
            // 如果子問題無解,則跳過循環(huán)
            if (i - coin < 0) {
                continue;
            }
            dp[i] = min(dp[i], 1 + dp[i - coin])
        }
     }
     return (dp[amount] == dp[amount + 1]) ? -1 : dp[amount];
}

• 數(shù)組之所以初始化為amount+1. 是因為湊成amount金額的硬幣數(shù)最多只可能等于amount, 全用面值為1元面值的硬幣時
• 初始化為amount+1就相當(dāng)于初始化為正無窮, 以便后續(xù)取最小值

總結(jié)

• 斐波那契問題:
  • 解釋了如何通過備忘錄或者DP Table的方法來優(yōu)化遞歸樹
  • 明確了這兩種方法本質(zhì)上是一樣的,只是自頂向下(備忘錄) 和自底向上(DP Table) 的不同
• 湊零錢問題:
  • 展示了如何流程化確定狀態(tài)轉(zhuǎn)移方程
  • 只要通過狀態(tài)轉(zhuǎn)義方程寫出直接遞歸的算法,然后就可以通過優(yōu)化遞歸樹,消除重疊子問題
• 計算機解決問題的唯一的解決辦法就是窮舉:
  • 窮舉所有可能性
  • 算法設(shè)計就是先思考如何窮舉
  • 然后再追求優(yōu)化窮舉的方式
• 如何窮舉: 列出動態(tài)轉(zhuǎn)移方程
  • 列出動態(tài)轉(zhuǎn)移方程就是在解決如何窮舉的問題.之所以列出動態(tài)轉(zhuǎn)移方程困難是因為:
  • 很多窮舉需要遞歸實現(xiàn)
  • 有的問題本身的解空間復(fù)雜,不容易窮舉完整
• 優(yōu)化窮舉的方式: 備忘錄和DP Table
  • 備忘錄和DP Table就是在追求優(yōu)化窮舉的方式
  • 運用的是用空間換時間的思路來降低算法時間復(fù)雜度