前言

之前我們簡單總結了一下動態規劃的解題套路，不少人反饋受益頗豐（如果是動態規劃初學者，強烈建議看看！）不過有位讀者說雖然動態規劃的解題套路是看懂了，不過一些動態規劃的主要特徵，如無後效性沒有提到，所以今天我們就簡單以一道題再來溫習一下動態規劃的解題套路及其主要特徵。

什麼樣的問題適合用動態規劃實現呢，我們在 一文學會動態規劃解題技巧 中曾經提到，只要問題符合「遞歸+重複」，則基本斷定可以用動態規劃來解題。簡單來說能用動態規劃解決的問題符合「一個模型三個特徵」

一個模型:多階段決策最優解模型，多階段意味着問題可以分解爲多個階段進行求解，每個階段通常都有一個最優解，每個階段的最優解通過遞推公式可以求得下個階段的最優解，求得了每個階段的最優解，自然而然全局最優解也就解決了

三個特徵

1. 最優子結構：上文一個模型中所述每個階段的最優解即最優子結構

2. 無後效性：當前階段的最優解只與它上個階段的最優解有關，它不 Care 上個階段的最優解是怎麼得來的，之後階段的決策（最優解）也不會影響之前階段問題的求解

3. 重複子問題: 如果問題採用自頂向下的方式解決，通常都會有重複子問題的，即我們所說的「遞歸+重複」，此時我們可以採用自下而上的套路來求解問題

如果大家對上文中的「一個模型三個特徵」沒感覺也沒關係，我們可以套用如下動態規劃解題模板

1. 判斷是否可用遞歸來解，可以的話進入步驟 2

2. 分析在遞歸的過程中是否存在大量的重複子問題

3. 採用備忘錄的方式來存子問題的解以避免大量的重複計算（剪枝）

4. 改用自底向上的方式來遞推，即動態規劃

接下來我們先通過一道比較有意思的習題來套用以上解題模板來解題，然後再來解釋一下動態規劃的「一個模型三個特徵」

問題定義

有如下 8 x 8 格子，機器人需要從開始位置走到結束位置,每次只能朝右或朝下走，粉色格子爲障礙物，機器人不能穿過，問機器人從開始位置走到結束位置最多共有多少種走法?

這題如果用動態規劃可能一時半會兒看不出來，那我們就用窮舉法來看看怎麼解，所謂窮舉法就是把機器人所有的路徑全部算出來,然後再相加

用窮舉法怎麼做呢，對於機器人起始位置來說，它可以選擇向下或向右,所以它到終點的路徑數爲其右邊格子到終點的路徑數與其下邊格子到終點的路徑數之和，僞代碼如下

paths(start, end) = paths(start下方格子， end) + paths(start右邊格子， end)

對於每個格子來說，它也可以選擇向左或向右，由於可以得出對於每個選中的格子，它都符合以下遞推公式:

paths(機器人所在格子, end) = paths(機器人所在格子下方格子， end) + paths(機器人所在格子右方格子， end)

表示成代碼如下:

private int countPaths(boolean[][] grid, int row, int col) {
    if(isObstacle(grid, row, col)) return 0;
        if (isAtEnd(grid, row, col)) return 1;
        return countPaths(grid, row+1, col) + countPath(grid, row, col+1)
}

看出規律了嗎，這其實是一個遞歸，那麼如果用遞歸會有什麼問題呢?

以上圖起始點出發爲例，如果選擇了向右或向下，則右或下格子也可以選擇向右或向下，如果右格子選擇向下，下格子選擇向右，則這兩條路徑都經過了相同的格子，這兩條路徑相交了！也就是出現了重複子問題！

每次機器人可以選擇向右或向下走，如果我們把它抽象成一顆二叉樹，則結構如下 ：

注：藍色代表相同的方塊

由於是一顆二叉樹，時間複雜度顯然是 O(2^n)，指數級別!原因當然是由於解題中存在大量的重複子問題（圖中藍色代表相同方塊，即重複子問題），爲了減少重複子問題，我們需要用備忘錄來保存中間的結果 （即減枝），這樣能讓時間複雜度大幅度減少，如下

經過「遞歸+備忘錄」後其實時間複雜度和動態規劃已經差不多了，不過我們之前一直強調儘量不要用遞歸的方式解題，因爲遞歸層級過深，很可能導致棧溢出。

所以接下來我們改用動態規劃的方式看看該如何解決。

遞歸是採用自頂向下的方式來解決問題，對應到本題，就是從起點出發，推導出到終點的所有路徑和，而動態規劃則是自下而上，即從終點出發推導出到起點的所有路徑和。對於最右邊和最底邊的格子來說，由於它們只能向下或向右走，所以分別在它們的位置上標 1，代表從這些格子出發只有一種路徑，如下圖示：

最右和最下邊的格子的路徑數都填上了，其它格子就簡單了，顯然對於其它格子來說，

paths(格子, end) = paths(下邊的格子， end) + paths(右邊的格子， end)

注：如果格子爲障礙物，則其到終點的路徑數爲 0

也就是說每個格子到終點的路徑和等於其右邊格子到終點的路徑數與其下邊格子到終點的路徑數之和，這樣從右到左，從下到上根據以上遞推公式依次填上每個格子的路徑數即可，如下

顯然從起點到終點的路徑和爲 10 + 17 = 27。時間複雜度是多少呢，從下到上，從右到左，兩層循環，顯然是 O(n^2)，比起最開始用遞歸的 O(2^n) 大幅度提升了。

知道解題思路，用代碼實現相信不是什麼大問題，我們以一個二維數組 grid[row][column] 來表示圖中的格子, 如果格子爲障礙物，則其元素值初始化爲 -1，其它格子元素初始化爲 0，這樣我們只要做個兩層循環即可求得最終的解，代碼如下，註釋很詳盡，相信大家應該能看懂

public class Solution {

    /**
     * 初始化格子， -1 代表格子爲障礙物
     */
    private static final int GRIDS[][] = {
            {0,0,0,0,0,0,0,0},
            {0,0,-1,0,0,0,-1,0},
            {0,0,0,0,-1,0,0,0},
            {-1,0,-1,0,0,-1,0,0},
            {0,0,-1,0,0,0,0,0},
            {0,0,0,-1,-1,0,-1,0},
            {0,-1,0,0,0,-1,0,0},
            {0,0,0,0,0,0,0,0}
    };

   static private int sumOfPaths() {

       // 格子爲 8 x 8
       int N = 8;
       /**
        * 初始化最右邊的格子
        */
       for (int j = 0; j < N; j++) {
           GRIDS[N-1][j] = 1;
       }

       /**
        * 初始化最底部的格子
        */
       for (int i = 0; i < N; i++) {
           GRIDS[i][N-1] = 1;
       }

       /**
        * 從右到左，從下到上填滿每個格子的值，由於最右和最底部的格子都初始化了，
        * 所以從倒數第二行，倒數第二列開始遍歷
        */
       for (int i = N - 2; i >= 0; i--) {
           for (int j = N - 2; j >= 0; j--) {
               // 說明是障礙物，無需計算
               if (GRIDS[i][j] == -1) {
                   continue;
               }

               /**
                * 每個要計算的格子到終點的路徑和等於其右邊格子到終點的路徑數與其下邊格子到終點的路徑數之和
                * 如果右邊或下邊的格子爲障礙物，則其到終點的路徑數設置爲 0
                */
               int rightPath = GRIDS[i+1][j] == -1 ? 0 : GRIDS[i+1][j];
               int bottomPath = GRIDS[i][j+1] == -1 ? 0 : GRIDS[i][j+1];
               GRIDS[i][j] = rightPath + bottomPath;
           }
       }

       /**
        * 遍歷完之後起點格子對應的值即爲最終所求的解
        */
       return GRIDS[0][0];
   }

    public static void main(String[] args) {
        int result = Solution.sumOfPaths();
        System.out.println("result = " + result);
    }
}    

可以看到，採用自底向上的動態規劃解法整體思路還是比較清晰且高效的。

問題解決了，現在我們回頭來看下動態規劃的一個模型和三個特徵該如何理解

一個模型:即多階段決策最優解模型，首先來看多階段，起始位置走向終點，第一階段可以看作是從起點向右或向下走，第一階段選中格子後，第二階段就要從第一階段選中的格子往右或往下走。。。，可以看到它的問題解確實是由多階段的最優組成的。

三個特徵

1、最優子結構

上文我們說對於每個格子，它到終點的路徑數爲其右邊格子到終點的路徑數與其下邊格子到終點的路徑數之和

paths(格子, end) = paths(下邊的格子， end) + paths(右邊的格子， end)

即對於每個格子來說，只要算出它的最優子結構（其右邊格子到終點的路徑數與其下邊格子到終點的路徑數），則此格子到終點的路徑和得出的就是最優解，進而可知上文中計算的 GRID[0][0] 也是全局最優解。

2、無後效性

每個格子到終點的路徑數只與其右邊格子到終點的路徑數與其下邊格子到終點的路徑數有關，它不 care 這兩者的路徑數是怎麼得出的，也就是當前階段的解只與它上一層階段的解有關，它並不關心這些解是怎麼算出來的，同時當前階段的解算完後，它並不會對之前的階段的解產生影響，這就是無後效性的含義。

3、 重複子問題

如果用遞歸的方式來做，我們之前分析過了，顯然存在重複子問題。

綜上，此題符合動態規劃的「一個模型三個特徵」，所以可以用動態規劃來解題

總結

本文用一道比較常見的習題來幫助大家重新溫習了一下動態規劃的特點：一個模型三個特徵，相信大家對這些概念應該有比較深刻的認識了，其實忘記這些概念，使用前文所述動態規劃解題四步曲基本可以套路大多數動態規劃的問題，不過了解這些概念能進一步地加深我們對動態規劃的理想，知其然，知其所以然也很重要。

最後，歡迎大家關注公衆號，加我好友，共同進步！

相關文章