【動態(tài)規(guī)劃】，Dynamic Programming, DP
過程：每次決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以這種多階段最優(yōu)化決策解決問題的過程 稱為【動態(tài)規(guī)劃】

思路

【動態(tài)規(guī)劃】是一種特殊的分治，與【分治算法】的思路類似：

• 將待求解的問題分解為若干個子問題（階段）
• 按順序求解子階段，前一子問題的解為后一子問題的求解提供了有用的信息；
• 在求解任一子問題時，列出各種可能的局部解，通過決策保留那些可能達到最優(yōu)的局部解，丟棄其他局部解；
• 依次解決各個子問題，最后一個子問題就是初始問題的解。

由于【動態(tài)規(guī)劃】解決的問題有重疊子問題的特點，為了讓每個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中，即 以空間換時間

與【分治算法】最大的區(qū)別是：適合于用【動態(tài)規(guī)劃】求解的問題，經(jīng)分解后得到的子問題往往【不是互相獨立的】，即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解。

特性

采用【動態(tài)規(guī)劃】求解的問題通常具備三個特性：

• 最優(yōu)子結構：（自上而下）
• 無后效性：某階段的狀態(tài)一旦確定，就不受之后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關，反之亦然。
• 重疊子問題：（自下而上）子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。
  這個性質(zhì)并不是【動態(tài)規(guī)劃】適用的必要條件，但如果沒有這條性質(zhì)，【動態(tài)規(guī)劃算法】同其他算法相比就不具備優(yōu)勢。

基本步驟

【動態(tài)規(guī)劃】所處理的問題是一個 多階段決策的問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結束狀態(tài)。
這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線（通常是求最優(yōu)活動路線）

初始狀態(tài) -> |決策-1| -> |決策-2| -> ... -> |決策-n| -> 結束狀態(tài)

• 【劃分階段】：按照問題的時間和空間特征，把問題劃分為若干個階段。注意：劃分后的階段一定要是有序的或可排序的，否則問題就無法求解。
• 【確定狀態(tài)和狀態(tài)變量】：將問題求解到各個階段時、所處于的各種客觀情況用不同的狀態(tài)表示出來，當然狀態(tài)的選擇要滿足【無后效性】
• 【確定決策并給出狀態(tài)轉移方程】：決策和狀態(tài)轉移有著天然聯(lián)系，【狀態(tài)轉移】就是根據(jù)上一階段的狀態(tài)和決策導出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉移方程也就可以寫出。但事實上，常常反過來做：根據(jù)相鄰兩個階段的狀態(tài)之間的聯(lián)系來確定決策方法和狀態(tài)轉移方程
• 【尋找邊界條件】：給出的狀態(tài)轉移方程是一個遞推式的，需要一個遞推的終止條件。

確定動態(tài)規(guī)劃的三要素：

• 問題的階段
• 每個階段的狀態(tài)
• 從前一個階段轉移到下一個階段之間的遞推關系

遞推關系 必須是從【次小問題】開始到【較大問題】之間的轉化，從這個角度來講，【動態(tài)規(guī)劃】往往可以用遞歸程序來實現(xiàn)，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢，這也就是【動態(tài)規(guī)劃算法】的核心之處。

確定了【動態(tài)規(guī)劃】的三要素之后，整個求解過程就可以用一個【最優(yōu)決策表】來描述，最優(yōu)決策表是一個二維表（或一維表）。其中，行表示決策的階段，列表示問題的狀態(tài)。表格需要填寫的數(shù)據(jù)一般對應此問題的在某個階段某個狀態(tài)下的最優(yōu)值（如最短路徑、最長公共子序列、最大價值等），填表的過程就是根據(jù)遞推關系，從1行1列開始，以行或列優(yōu)先的順序，一次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)、通過簡單的取舍或運算求得問題的最優(yōu)解。

f(n, m) = max{ f(n-1, m), f(n-1, m - w[n]) + P(n, m) }

動態(tài)規(guī)劃的解題套路

【動態(tài)規(guī)劃】無非就是利用 歷史記錄 來避免重復計算，而這些歷史記錄一般使用 一維數(shù)組 或 二維數(shù)組 來保存。

• 步驟一：定義數(shù)組元素的含義。可以理解為拆分成子問題
  數(shù)組是用來保存歷史記錄的，那么就必須規(guī)定數(shù)組元素的含義。假設使用一維數(shù)組dp，規(guī)定 dp[i]代表什么意思
• 步驟二：數(shù)組元素之間的關系式?？梢岳斫鉃樽訂栴}重疊
  類似數(shù)學歸納法，當計算 dp[n] 時，可以利用dp[n-1]、dp[n-2]、...、dp[1] 來推導dp[n]，也可以利用歷史數(shù)據(jù)來推導新的元素值，比如dp[n] = dp[n-1] + dp[n-2]，這就是元素之間的關系式。
• 步驟三：初始值。對于數(shù)學歸納法，雖然知道了元素之間的關系式，但必須知道初始值。比如dp[n] = dp[n-1] + dp[n-2]，一直推導直到dp[3] = dp[2] + dp[1]，而 dp[2] 和 dp[1] 是不可分解的，所以必須能夠獲取dp[2] 和 dp[1]的值，即 初始值。

一維數(shù)組 之 青蛙跳臺階

正常青蛙

問題：一只青蛙一次跳 1 個臺階，也可以跳 2 個臺階，請問 跳 N 個臺階有多少種跳法？

• 定義 數(shù)組元素的含義
  問題是求青蛙跳上 n 級臺階總共由多少種跳法，那么就可以用一個一維數(shù)組來保存跳法，定義 dp[i] 的含義為：跳上一個 i 級臺階總共有 dp[i] 種跳法。計算出 dp[n] 也就是需要的答案。

• 找出 數(shù)組元素間的關系式
  【動態(tài)規(guī)劃】也是把一個規(guī)模較大的問題分解成規(guī)模較小的子問題，解出小問題推導出大問題的解。dp[n]的規(guī)模為n，比它規(guī)模小的是n-1、n-2、n-3...，也就是說dp[n] 一定和dp[n-1]、dp[n-2]、...存在某種關系。
  分析：
  青蛙一次可以跳 1 或 2 個臺階，那么跳上n 個臺階的跳法f(n)就有兩種情況：

  • 從第 (n-1) 個臺階跳 1 階，這類跳法有f(n-1)種
  • 從第 (n-2) 個臺階跳 2 階，這類跳法有f(n-2)種

  可以得出，跳到 n 個臺階的跳法 等于 跳到 n-1 個臺階 與 跳到 n-2 個臺階之和，即f(n) = f(n-1) + f(n-2)，類似斐波那契數(shù)列，反映到數(shù)組元素的關系式為 dp[n] = dp[n-1] + dp[n-2]

• 找出 初始值
  當 n = 1，時，dp[1] = dp[0] + dp[-1]，而數(shù)組下標不允許為負數(shù)，所以必須直接給出 dp[1] 的值，dp[1] = 1，即 初始值。
  同理，n = 0表示沒有跳臺階，即dp[0] = 0，而dp[2] = dp[1] + dp[0] = 1 + 0 = 1，而實際上dp[2] = 2，所以 初始值 的設定為 n <= 2 時，dp[n] = n

# 迭代版本
function jump(n){
    if(n <= 2){
        return n;
    }
    // 假裝使用數(shù)組：這樣會造成空間復雜度為 O(n)
    // 其實可以直接使用 【變量】 代替，這樣空間復雜度優(yōu)化成 O(1)
    let dp = [0, 1, 2]
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

# 遞歸版本
function jump(n, start = 1, end = 1){
    if(n <= 2){
        return n
    }
    return jump(n - 1) + jump(n - 2)
}

# 尾遞歸優(yōu)化
function jump(n, start = 1, end = 0){
    if(n === 0){
        return end;
    } else if(start === 0) {
        start = 1
    }
    return jump(n - 1, end, start + end);
}

變異青蛙

問題：一只青蛙一次跳 1 個臺階，也可以跳 2 個臺階、3個臺階、4個臺階、...、n個臺階，請問 跳 N 個臺階有多少種跳法？
分析：同理，跳上 n 級臺階有 n 種跳法，f(n) = f(n-1) + f(n-2) + ... + f(1)
又由 f(n-1) = f(n-2) + f(n-3) + ... + f(1) 可知，f(n) = 2f(n-1) = 2^(n-1)*f(1) = 2^(n-1)*1
得：f(n) = 2^(n-1)，n > 2。當n <= 2 時，f(n) = n

二維數(shù)組

其實，【動態(tài)規(guī)劃】解題時大多數(shù)使用的都是 二維數(shù)組

機器人走方格（路徑規(guī)劃）

一個機器人位于 M x N 網(wǎng)格的左上角，每次只能向下或向右移動一步，到達網(wǎng)格右下腳一共有多少條不同的路徑？

機器人走網(wǎng)格

• 步驟一：定義數(shù)組元素的含義
  既然是一個M x N的網(wǎng)格，那么元素dp[i][j] 就表示其中一個格子，dp[0][0] 表示左上角，dp[m-1][n-1] 表示右下角。
  數(shù)組元素 dp[i][j] 的含義：當機器人從左上角走到(i, j)位置時，一共有 dp[i][j] 種路徑。

• 步驟二：分析數(shù)組元素之間的關系式
  機器人可以向下走，也可以向右走，所以到達 dp[i][j] 位置有兩種方式

  • 從 dp[i-1][j] 位置走一步達到
  • 從 dp[i][j-1] 位置走一步達到

  計算所有可能的方式 就是把走的路徑相加，所以關系式為 dp[i][j] = dp[i-1][j] + dp[i][j-1]

• 步驟三：確定初始值
  對于dp[i][j]，如果 i = 0 或 j = 0，關系式就不再成立了，因為數(shù)組角標不能為負數(shù)。
  所以，初始值就是算出所有的dp[0][0] + dp[0][1] + ... + d[0][n-1] 和所有的dp[0][0] + dp[1][0] + ... + dp[m-1][0]，它們分別表示：一直右走（一條路徑）、一直向下走（一條路徑）
  得初始值：

  • dp[0][0...n-1] = 1 一直向右走
  • dp[0...m-1][0] = 1 一直向下走

public int solution(int m, int n) {
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

空間復雜度的優(yōu)化：由狀態(tài)轉移方程式dp[i][j] = dp[i-1][j] + dp[i][j-1] 可知，當填充第 i 行的值時，只需要知道第i-1行的值，從第1行到第i-2行都是不需要的！
https://zhuanlan.zhihu.com/p/91582909

進階版

保持問題的題意，在網(wǎng)格中增加障礙物，機器人無法越過障礙物
分析：雖然增加了障礙物，但關系式還是適用的，不過需要些許改變

• 對于正下方和正右方的路徑，一旦遇到障礙物，就表示無法通過，則后面的路徑全是0
• 障礙物所處的點本身不可達，也導致后面的所有點都不可達，即存儲值為0

// 給定一個二維數(shù)組，如果某個元素值為 1，表示有障礙物
public int uniquePathsWithObstacles(int[][] matrix) {
    if(matrix == null) return 0;
    if(matrix[0][0] == 1) {  // 起點有障礙物，不可達
        return 0;
    }
    int row = matrix.length;
    int col = matrix[0].length;
    if(matrix[row-1][col-1] == 1) {  // 重點有障礙物，不可達
        return 0;
    }
    // 構建路徑二維數(shù)組
    int[][] dp = new int[row][col];
    // 初始化起點，開始有 1 條路徑
    dp[0][0] = 1;
    // 第一列: 初始化值都是 1
    for(int i = 1; i < row; i++) {
        if(matrix[i][0] != 1) {  // 沒有障礙物
            dp[i][0] = dp[i-1][0];
        }
    }
    // 第一行: 初始化值都是 1
    for(int j = 1; j < col; j++) {
        if(matrix[0][j] != 1) {  // 沒有障礙物
            dp[0][j] = dp[0][j-1];
        }
    }
    // 計算其他所有路徑
    for(int i = 1; i < row; i++) {
        for(int j = 1; j < col; j++) {
            if(matrix[i][j] == 1) continue;  // 障礙物
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[row-1][col-1];
}

最小路徑之和

給定一個M x N的網(wǎng)格，每次只能向下或向右移動一格，請找出一條從左上角到左下角的路徑，使得路徑上的數(shù)字總和最小。

arr = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
// 最小路徑 1 -> 3 -> 1 -> 1 -> 1，總和為 7

• 步驟一：定義數(shù)組元素的含義
  dp[i][j] 的含義：從左上角(0, 0)走到坐標(i, j)的位置時，最小路徑之和為d[i][j]。
  那么，d[m-1][n-1] 即是右下角的最小路徑之和。

• 步驟二：數(shù)組元素間的關系式
  走到 (i, j) 位置的方式有兩種：

  • 從 (i-1, j) 向下走一步到達
  • 從(i, j-1)向右走一步到達

  不同的是，這次不是計算所有可能的路徑，而是計算哪一條路徑之和最小，所以要從這兩種方式中選擇一條路徑、使得 dp[i][j] 的值最小。
  則有：

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

• 步驟三：初始值
  數(shù)組角標的最小值為 0，所以(i、j) >= 0。初始值也就是計算出所有的dp[0][0...n-1] 和 dp[0...m-1][0]，分別是第一行和第一列。

  // 第一行的路徑之和
  dp[0][j] = arr[0][j] + dp[0][j-1]
  // 第一列的路徑之和
  dp[i][0] = arr[i][0] + dp[i-1][0]
  

public int uniquePath(int[][] arr) {
    int row = arr.length;
    if(row == 0) return 0;
    int col = arr[0].length;
    if(col == 0) return 0;
    
    int[][] dp = new int[row][col];
    // 初始化
    dp[0][0] = arr[0][0];
    // 第一列的初始化
    for(int i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] + arr[i][0];
    }
    // 第一行的初始化
    for(int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j-1] + arr[0][j];
    }
    // 推導 dp[row-1][col-1]
    for(int i = 1; i < row; i++) {
        for int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
        }
    }
    return dp[row-1][col-1];
}
// O(n*m) 的空間復雜度可以優(yōu)化成 O(min(n, m)) 的空間復雜度

編輯距離

給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少操作數(shù)？
可以對一個單詞進行三種操作：

• 插入一個字符
• 刪除一個字符
• 替換一個字符

# 舉個栗子
word1 = "horse", word2 = "ros"
// 最小操作數(shù) 3
horse -> rorse (將 h 替換成 r)
rorse -> rose  (刪除 r)
rose  -> ros   (刪除 e)

步驟一：定義數(shù)組元素的含義

目的是求 word1 轉換成 word2 所使用的最少操作數(shù)，那么就定義 dp[i][j] 的含義為：當字符串word1 的長度為i、字符串word2 的長度為j 時，將 word1 轉為 word2 所使用的最少操作數(shù)為dp[i][j]。

步驟二：數(shù)組元素之間的關系式

關系式的推導往往是從小規(guī)模到大規(guī)模的過程，也就是說，dp[i][j] 通常都會與 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 存在某種關系。
分析：
由題可知：對 word1 的操作有三種：插入、刪除、替換 一個字符
要想讓操作的次數(shù)最小，就要尋找最佳操作：

• 如果word1[i] == word2[j]，則不需要做任何操作，那么把【字符串word1 的前 i 個字符】轉化為【字符串word2 的前 j 個字符】的操作步數(shù) 與 【前i-1】轉換成【前j-1】的操作步數(shù)是相等的，即 dp[i][j] = dp[i-1][j-1]
• 如果word1[i] != word2[j]，那么就必須對字符串word1 進行調(diào)整，且有三種操作可選：
  • 刪除
    想象一下，什么情況下僅僅對word1 刪除一個元素就可以完成【前i 個字符轉換成word2 的前j 個字符】呢？
    刪除一個字符，意味著【word1的前i-1 個字符已經(jīng)轉換成了word2 的前j 個字符】，所以對word1 的轉換就是 刪除第i個字符 這一個操作步數(shù)。
    可得表達式：dp[i][j] = dp[i-1][j] + 1
  • 插入
    對word1 插入一個字符才能完成轉換，也就是說已經(jīng)將word1 的前i個字符轉換成了word2 的前j-1 個字符，那么現(xiàn)在只需要再對word1 追加一個與【word2 的第j 個字符】相等的字符就完成了。
    因此可得：dp[i][j] = dp[i][j-1] + 1
  • 替換
    將word1 的第 i 個字符替換成 word2 的第 j 個字符，也就是說【word1的前i-1個字符】已經(jīng)轉換成了【word2的前j-1個字符】，再跟進 替換 這一步即可。
    可得關系式：dp[i][j] = dp[i-1][j-1] + 1

至此，通過三種操作得到了三種dp[i][j]的關系式，并且利用了之前保存的狀態(tài)，所以只需要 取其中最少的步數(shù) 即可的得到原問題的解。
總關系式：

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

步驟三：初始值

數(shù)組角標不能為負數(shù)，而當 i=0 或 j=0 時，關系式中的 i - 1 和 j - 1 就得到了負數(shù)的角標。所以，初始值就是計算出所有dp[0][0...j]和所有的dp[0...i][0]。
由二維數(shù)組dp 的含義可知，角標表示兩個字符串的長度，當i=0 或 j=0時，也就是有一方字符串的長度為0，那么只需要 刪除 或 插入 操作即可。

• 對于dp[0][j]來說，將長度為 0 的字符串word1 轉換成長度為 j 的字符串word2，只需要不斷地對word1 執(zhí)行 插入操作，總操作步數(shù)為j

  dp[0][j] = j
  

• 同理，對于dp[i][0]，則不斷地對word1 執(zhí)行 刪除操作，總操作步數(shù)為i

  dp[i][0] = i
  

實現(xiàn)代碼

function convert(s1, s2) {
    let m = s1.length
    let n = s2.length
    // 構建二維數(shù)組：長度比字符串大 1，是因為關系式的角標不能為 0
    let dp = new Array(m+1).fill(new Array(n+1))
    // dp[0...m][0] 初始化
    for(let i = 0; i < m+1; i++) {
        dp[i][0] = i
    }
    // dp[0][0...n] 初始化
    for(let j = 0; j < n+1; j++) {
        dp[0][j] = j
    }
    // 數(shù)組元素之間的關系
    for(let i = 1; i < m+1; i++) {
        for(let j = 1; j < n+1; j++) {
            if(s1[i-1] === s2[j-1]) {
                // 兩個字符相等，則無需操作，即操作步數(shù)與前一步相等
                dp[i][j] = dp[i-1][j-1]
            } else {
                // 取最小操作步數(shù) + 1 就是當前操作步數(shù)
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
        }
    }
    return dp[m][n]
}