動(dòng)態(tài)規(guī)劃的三大步驟

動(dòng)態(tài)規(guī)劃，無非就是利用歷史記錄，來避免我們的重復(fù)計(jì)算。而這些歷史記錄，我們得需要一些變量來保存，一般是用一維數(shù)組或者二維數(shù)組來保存。下面我們先來講下做動(dòng)態(tài)規(guī)劃題很重要的三個(gè)步驟。

• 1. 定義數(shù)組元素的含義
     我們會(huì)用一個(gè)數(shù)組，來保存歷史數(shù)組，假設(shè)用一維數(shù)組 dp[] 吧。這個(gè)時(shí)候有一個(gè)非常非常重要的點(diǎn)，就是規(guī)定你這個(gè)數(shù)組元素的含義，例如你的 dp[i] 是代表什么意思？
• 2. 找出數(shù)組元素之間的轉(zhuǎn)移方程
     動(dòng)態(tài)規(guī)劃，有一點(diǎn)類似于我們高中學(xué)習(xí)時(shí)的歸納法的，當(dāng)我們要計(jì)算 dp[n] 時(shí)，是可以利用 dp[n-1]，dp[n-2].....dp[1]，來推出 dp[n] 的，也就是可以利用歷史數(shù)據(jù)來推出新的元素值，所以我們要找出數(shù)組元素之間的關(guān)系式，例如 dp[n] = dp[n-1] + dp[n-2]，這個(gè)就是他們的關(guān)系式了。而這一步，也是最難的一步，后面我會(huì)講幾種類型的題來說。
• 3. 找出初始值
     學(xué)過數(shù)學(xué)歸納法的都知道，雖然我們知道了數(shù)組元素之間的關(guān)系式，例如 dp[n] = dp[n-1] + dp[n-2]，我們可以通過 dp[n-1] 和 dp[n-2] 來計(jì)算 dp[n]，但是，我們得知道初始值啊，例如一直推下去的話，會(huì)由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我們必須要能夠直接獲得 dp[2] 和 dp[1] 的值，而這，就是所謂的初始值。由了初始值，并且有了數(shù)組元素之間的關(guān)系式，那么我們就可以得到 dp[n] 的值了，而 dp[n] 的含義是由你來定義的，你想求什么，就定義它是什么，這樣，這道題也就解出來了。

案例一

最小路徑和(leetcode 的第64題)

• 問題描述
  給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。說明：每次只能向下或者向右移動(dòng)一步。舉例：
  輸入:
  arr = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
  ]
  輸出: 7
  解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。
• 1. 定義數(shù)組元素的含義
     由于我們的目的是從左上角到右下角，最小路徑和是多少，那我們就定義 dp[i] [j]的含義為：當(dāng)機(jī)器人從左上角走到(i, j) 這個(gè)位置時(shí)，最下的路徑和是 dp[i] [j]。那么，dp[m-1] [n-1] 就是我們要的答案了。

注意，這個(gè)網(wǎng)格相當(dāng)于一個(gè)二維數(shù)組，數(shù)組是從下標(biāo)為 0 開始算起的，所以 由下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我們要走的答案。

• 2. 找出關(guān)系數(shù)組元素間的轉(zhuǎn)移方程
     想象一下，機(jī)器人要怎么樣才能到達(dá) (i, j) 這個(gè)位置？由于機(jī)器人可以向下走或者向右走，所以有兩種方式到達(dá)一種是從 (i-1, j) 這個(gè)位置走一步到達(dá)，另一種是從(i, j - 1) 這個(gè)位置走一步到達(dá)不過這次不是計(jì)算所有可能路徑，而是計(jì)算哪一個(gè)路徑和是最小的，那么我們要從這兩種方式中，選擇一種，使得dp[i] [j] 的值是最小的，顯然有

dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j];// arr[i][j] 表示網(wǎng)格種的值

• 3. 找出初始值。
     當(dāng) dp[i] [j] 中，如果 i 或者 j 有一個(gè)為 0，那么還能使用關(guān)系式嗎？答是不能的，因?yàn)檫@個(gè)時(shí)候把 i - 1 或者 j - 1，就變成負(fù)數(shù)了，數(shù)組就會(huì)出問題了，所以我們的初始值是計(jì)算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。這個(gè)還是非常容易計(jì)算的，相當(dāng)于計(jì)算機(jī)圖中的最上面一行和左邊一列。
     因此初始值如下：

dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相當(dāng)于最上面一行，機(jī)器人只能一直往左走
dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相當(dāng)于最左面一列，機(jī)器人只能一直往下走

代碼如下

public static int uniquePaths(int[][] arr) {
    int m = arr.length;
    int n = arr[0].length;
    if (m <= 0 || n <= 0) {
        return 0;
    }

    int[][] dp = new int[m][n]; // 
    // 初始化
    dp[0][0] = arr[0][0];
    // 初始化最左邊的列
    for(int i = 1; i < m; i++){
      dp[i][0] = dp[i-1][0] + arr[i][0];
    }
    // 初始化最上邊的行
    for(int i = 1; i < n; i++){
      dp[0][i] = dp[0][i-1] + arr[0][i];
    }
        // 推導(dǎo)出 dp[m-1][n-1]
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
        }
    }
    return dp[m-1][n-1];
}

案例二

編輯距離(leetcode 的第題72)

• 問題描述
  給定兩個(gè)單詞 word1 和 word2，計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：插入一個(gè)字符 刪除一個(gè)字符 替換一個(gè)字符示例：

輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')

• 解答
  還是老樣子，按照上面三個(gè)步驟來，并且我這里可以告訴你，90% 的字符串問題都可以用動(dòng)態(tài)規(guī)劃解決，并且90%是采用二維數(shù)組。
• 定義數(shù)組元素的含義
  由于我們的目的求將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。那我們就定義 dp[i] [j]的含義為：當(dāng)字符串 word1 的長(zhǎng)度為 i，字符串 word2 的長(zhǎng)度為 j 時(shí)，將 word1 轉(zhuǎn)化為 word2 所使用的最少操作次數(shù)為 dp[i] [j]。

有時(shí)候，數(shù)組的含義并不容易找

• 找出關(guān)系數(shù)組元素間的轉(zhuǎn)移方程
  接下來我們就要找 dp[i] [j] 元素之間的關(guān)系了，大部分情況下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某種關(guān)系。因?yàn)槲覀兊哪繕?biāo)就是，從規(guī)模小的，通過一些操作，推導(dǎo)出規(guī)模大的。
  對(duì)于這道題，我們可以對(duì) word1 進(jìn)行三種操作：插入一個(gè)字符 刪除一個(gè)字符 替換一個(gè)字符。由于我們是要讓操作的次數(shù)最小，所以我們要尋找最佳操作。
  那么有如下關(guān)系式：
  • 1. 如果我們 word1[i] 與 word2 [j] 相等，這個(gè)時(shí)候不需要進(jìn)行任何操作，顯然有 dp[i] [j] = dp[i-1] [j-1]。（別忘了 dp[i] [j] 的含義哈）。
  • 2. 如果我們 word1[i] 與 word2 [j] 不相等，這個(gè)時(shí)候我們就必須進(jìn)行調(diào)整，而調(diào)整的操作有 3 種，我們要選擇一種。三種操作對(duì)應(yīng)的關(guān)系試如下（注意字符串與字符的區(qū)別）：
    • 1. 如果把字符 word1[i] 替換成與 word2[j] 相等，則有 dp[i] [j] = dp[i-1] [j-1] + 1。
    • 2. 如果在字符串 word[i]末尾插入一個(gè)與 word2[j] 相等的字符，則有 dp[i] [j] = dp[i] [j-1] + 1。
    • 3. 如果把字符 word1[i] 刪除，則有 dp[i] [j] = dp[i-1] [j] + 1。

我們應(yīng)該選擇一種操作，使得 dp[i] [j] 的值最小，顯然有

dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1

• 找出初始值
  顯然，當(dāng) dp[i] [j] 中，如果 i 或者 j 有一個(gè)為 0，那么還能使用關(guān)系式嗎？答是不能的，因?yàn)檫@個(gè)時(shí)候把 i - 1 或者 j - 1，就變成負(fù)數(shù)了，數(shù)組就會(huì)出問題了，所以我們的初始值是計(jì)算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。這個(gè)還是非常容易計(jì)算的，因?yàn)楫?dāng)有一個(gè)字符串的長(zhǎng)度為 0 時(shí)，轉(zhuǎn)化為另外一個(gè)字符串，那就只能一直進(jìn)行插入或者刪除操作了。

代碼如下

public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    // dp[0][0...n2]的初始值
    for (int j = 1; j <= n2; j++) 
        dp[0][j] = dp[0][j - 1] + 1;
    // dp[0...n1][0] 的初始值
    for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
        // 通過公式推出 dp[n1][n2]
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            // 如果 word1[i] 與 word2[j] 相等。第 i 個(gè)字符對(duì)應(yīng)下標(biāo)是 i-1
            if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                p[i][j] = dp[i - 1][j - 1];
            }else {
               dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }         
        }
    }
    return dp[n1][n2];  
}

優(yōu)化

畫圖！畫圖！畫圖

80% 的動(dòng)態(tài)規(guī)劃題都可以畫圖，其中 80% 的題都可以通過畫圖一下子知道怎么優(yōu)化，當(dāng)然，DP 也有一些很難的題，想優(yōu)化可沒那么容易，不過，今天我要講的，是屬于不怎么難，且最常見，面試筆試最經(jīng)?？嫉碾y度的題。下面我們直接通過三道題目來講解優(yōu)化，你會(huì)發(fā)現(xiàn)，這些題，優(yōu)化過后，代碼只有細(xì)微的改變，你只要會(huì)一兩道，可以說是會(huì)了 80% 的題。

案例一（最短路徑數(shù)）優(yōu)化
前面的做法的空間復(fù)雜度是 O(n * m)，下面我們來講解如何優(yōu)化成 O(n)。
dp[i] [j] 是一個(gè)二維矩陣，我們來畫個(gè)二維矩陣的圖，對(duì)矩陣進(jìn)行初始化。
然后根據(jù)公式 dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j] 來填充矩陣的其他值。
根據(jù)公式 我們知道當(dāng)我們要填充某一行的值的時(shí)候，我們只需要用到上一行的值，而不需要用到更前面的行的值，也就是說，我們只需要用一個(gè)一維的 dp[] 來保存一行的歷史記錄就可以了，然后在計(jì)算機(jī)的過程中，不斷著更新 dp[] 的值。

畫圖演示下這個(gè)過程

• 原始數(shù)據(jù)

• 根據(jù)原始數(shù)據(jù)，算出第一行。

• 根據(jù)原始數(shù)據(jù)和第一行算出第二行

• 根據(jù)原始數(shù)據(jù)和第二行算出第三行

最后得到結(jié)果 7

轉(zhuǎn)移方程
由
dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]
變?yōu)?br> dp[j] = Math.min(dp[j], dp[j - 1]) + arr[i][j]

優(yōu)先代碼后代碼

      public static int uniquePaths(int[][] arr) {
        int n = arr[0].length;
        int[] dp = new int[n]; //
        // 初始化最上邊的行
        dp[0] = arr[0][0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + arr[0][i];
        }
        // 推導(dǎo)出 dp[n-1]
        for (int i = 1; i < arr.length; i++) {
            dp[0] = dp[0] + arr[i][0];//j為0的時(shí)候直接在累加當(dāng)前單元格的值
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + arr[i][j];
            }
        }
        return dp[n - 1];
    }

Leetcode 動(dòng)態(tài)規(guī)劃直達(dá)：https://leetcode-cn.com/tag/dynamic-programming/
參考：https://www.zhihu.com/question/291280715/answer/1570410869