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

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

• 什么叫作最優(yōu)子結(jié)構(gòu)? 和動態(tài)規(guī)劃有什么關(guān)系?
• 為什么動態(tài)規(guī)劃遍歷DP數(shù)組的方式有正著遍歷,有倒著遍歷,有斜著遍歷?

最優(yōu)子結(jié)構(gòu)

• 最優(yōu)子結(jié)構(gòu)是某些問題的一種特定的性質(zhì),并不是動態(tài)規(guī)劃問題所特有的.
• 很多問題都具有最優(yōu)子結(jié)構(gòu),但是其中大部分不具有重疊子問題,所以不會歸為動態(tài)規(guī)劃系列的問題
• 最優(yōu)子結(jié)構(gòu):
  • 可以從子問題的最優(yōu)結(jié)果推導(dǎo)出更大規(guī)模問題的最優(yōu)結(jié)果
  • 子問題之間必須相互獨立
• 通過改造問題來優(yōu)化由于子問題之間不獨立而導(dǎo)致的最優(yōu)子結(jié)構(gòu)失效的情況:
  • 問題: 假設(shè)學(xué)校有10個班,已知每個班的最高分與最低分差值的最大分?jǐn)?shù)差,需要計算全校學(xué)生中的最大分?jǐn)?shù)差
  • 分析: 這樣的問題就無法通過這10個班的最大分?jǐn)?shù)差來推導(dǎo)出來,因為這10個班的最大分?jǐn)?shù)差不一定就包含全校學(xué)生的最大分?jǐn)?shù)差.比如全校的最大分?jǐn)?shù)差可能是由8班的最高分和6班的最低分的分?jǐn)?shù)差而得.這樣就導(dǎo)致子問題之間不是互相獨立的
  • 改造問題: 直接進行問題改造

  int result = 0;
  for (Student a : school) {
    for (Student b : school) {
        if (a is b) {
            continue;
        } 
        result = max(result, |a.score - b.score|)
    }
  }
  return result;
  

• 改造問題就是將問題等價轉(zhuǎn)化:
  • 最大分?jǐn)?shù)差就等價于最高分?jǐn)?shù)與最低分?jǐn)?shù)的差
  • 那么就是要求最高和最低分?jǐn)?shù)
  • 求最高分?jǐn)?shù)是具備最優(yōu)子結(jié)構(gòu)的,求最低分?jǐn)?shù)也是具有最優(yōu)子結(jié)構(gòu)的
  • 這樣就樣一個不具備最優(yōu)子結(jié)構(gòu)的問題轉(zhuǎn)化為具備最優(yōu)子結(jié)構(gòu)的子問題
  • 借助最優(yōu)子結(jié)構(gòu)解決最值問題,再解決最大分?jǐn)?shù)差問題
• 題目: 求一棵二叉樹的最大值,假設(shè)節(jié)點中的值都為非負數(shù)

int maxVal(TreeNode root) {
    if (root == null) {
        return -1;
    }
    int left = maxVal(root.left);
    int right = maxVal(root.right);
    return max(root.val, left, right);
}

這個問題符合最優(yōu)子結(jié)構(gòu),以root為根的樹的最大值可以通過兩邊子樹的子問題的最大值推導(dǎo)出來

最優(yōu)子結(jié)構(gòu)總結(jié)

• 最優(yōu)子結(jié)構(gòu)并不是動態(tài)規(guī)劃獨有的一種性質(zhì),但是能求最值的問題大部分都會具備最優(yōu)子結(jié)構(gòu)的性質(zhì)
• 最優(yōu)子結(jié)構(gòu)性質(zhì)作為動態(tài)規(guī)劃問題的必要條件,一定是可以用來求最值的: 通常情況下,最值的問題,思路往動態(tài)規(guī)劃想就對了
• 動態(tài)規(guī)劃就是從最簡單的base case往后推導(dǎo), 類似一種鏈?zhǔn)椒磻?yīng).但是只有具備最優(yōu)子結(jié)構(gòu)的問題,才會有發(fā)生這種鏈?zhǔn)椒磻?yīng)的性質(zhì)
• 最優(yōu)子結(jié)構(gòu)的尋找過程:
  • 就是證明狀態(tài)轉(zhuǎn)移方程正確性的過程
  • 方程符合最優(yōu)子結(jié)構(gòu)就可以直接遞歸求解
  • 寫出直接遞歸求解后可以根據(jù)遞歸樹看出有沒有重疊子問題,如果有則進行優(yōu)化

DP數(shù)組的遍歷方向

• 動態(tài)規(guī)劃中DP數(shù)組遍歷順序問題:
  • 示例: 二維DP數(shù)組
    • 正向遍歷:

    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            /*
             * 計算dp[i][j]
             */  
             ...
        }   
    }   
    

    • 反向遍歷:

    int[][] dp = new int[m][n];
    for (int i = m-1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            /*
             * 計算dp[i][j]
             */
             ...
        }
    }
    

    • 斜向遍歷:

    int[][] dp = new int[m][n];
    for (int l = 2; l <= n; l++) {
        for (int i = 0; i <= n - l; i++) {
            int j = l + i - 1;
            /*
             * 計算dp[i][j]
             */
        }
    }
    

• DP數(shù)組的遍歷的兩條原則:
  • 遍歷的過程中,所需的狀態(tài)必須是已經(jīng)計算出來的
  • 遍歷的終點必須是存儲結(jié)果的位置

編輯距離問題

• 通過對DP數(shù)組的定義,確定了:
  • base case : dp[n][0] 和dp[0][n]
  • 最終答案 : dp[m][n]
• 通過狀態(tài)轉(zhuǎn)移方程知道:
  • dp[i][j] 需要從dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 轉(zhuǎn)移而來
• 再根據(jù)DP數(shù)組遍歷的兩條原則,確定使用正向遍歷:

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        /*
         * 通過dp[i-1][j], dp[i][j-1], dp[i-1][j-1]計算dp[i][j]
         */
    }
}

• 這樣每一步迭代的左邊,上邊,左上邊的位置都是base case或者之前計算出來的值
• 最終結(jié)束在結(jié)果的位置dp[m][n]

回文子序列

• 通過對DP數(shù)組的定義,確定了:
  • base case處在中間的對角線
  • 最終答案: dp[0][n-1]
• 通過狀態(tài)轉(zhuǎn)移方程知道:
  • dp[i][j] 需要從dp[i+1][j], dp[i][j-1], dp[i+1][j-1] 轉(zhuǎn)移而來
• 再根據(jù)DP數(shù)組遍歷的兩條原則,確定有兩種遍歷方式:
  • 從左至右斜著遍歷
  • 從下向上從左到右遍歷
• 這樣每一步迭代的左邊,下邊,左下邊已經(jīng)計算出來值
• 最終結(jié)束在結(jié)果的位置 dp[0][n-1]

DP數(shù)組遍歷總結(jié)

• DP數(shù)組遍歷主要就是看base case和最終結(jié)果的存儲位置類決定遍歷順序
• 選擇的遍歷順序要保證遍歷過程中使用的數(shù)據(jù)都是計算完畢的