面試官：換人！他連動態規劃的一個模型三個特征都不懂
前言
之前我們簡單總結了一下動態規劃的解題套路，不少人反饋受益頗豐(如果是動態規劃初學者，強烈建議看看!)不過有位讀者說雖然動態規劃的解題套路是看懂了，不過一些動態規劃的主要特征，如無后效性沒有提到，所以今天我們就簡單以一道題再來溫習一下動態規劃的解題套路及其主要特征。
什么樣的問題適合用動態規劃實現呢，我們在一文學會動態規劃解題技巧中曾經提到，只要問題符合「遞歸+重復」，則基本斷定可以用動態規劃來解題。簡單來說能用動態規劃解決的問題符合「一個模型三個特征」
一個模型: 多階段決策最優解模型，多階段意味著問題可以分解為多個階段進行求解，每個階段通常都有一個最優解，每個階段的最優解通過遞推公式可以求得下個階段的最優解，求得了每個階段的最優解，自然而然全局最優解也就解決了
三個特征
- 最優子結構：上文一個模型中所述每個階段的最優解即最優子結構
- 無后效性：當前階段的最優解只與它上個階段的最優解有關，它不 Care 上個階段的最優解是怎么得來的，之后階段的決策(最優解)也不會影響之前階段問題的求解
- 重復子問題: 如果問題采用自頂向下的方式解決，通常都會有重復子問題的，即我們所說的「遞歸+重復」，此時我們可以采用自下而上的套路來求解問題
如果大家對上文中的「一個模型三個特征」沒感覺也沒關系，我們可以套用如下動態規劃解題模板
- 判斷是否可用遞歸來解，可以的話進入步驟 2
- 分析在遞歸的過程中是否存在大量的重復子問題
- 采用備忘錄的方式來存子問題的解以避免大量的重復計算(剪枝)
- 改用自底向上的方式來遞推，即動態規劃
接下來我們先通過一道比較有意思的習題來套用以上解題模板來解題，然后再來解釋一下動態規劃的「一個模型三個特征」
問題定義
有如下 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、 重復子問題
如果用遞歸的方式來做，我們之前分析過了，顯然存在重復子問題。
綜上，此題符合動態規劃的「一個模型三個特征」，所以可以用動態規劃來解題
總結本文用一道比較常見的習題來幫助大家重新溫習了一下動態規劃的特點：一個模型三個特征，相信大家對這些概念應該有比較深刻的認識了，其實忘記這些概念，使用前文所述動態規劃解題四步曲基本可以套路大多數動態規劃的問題，不過了解這些概念能進一步地加深我們對動態規劃的理想，知其然，知其所以然也很重要。
本文轉載自微信公眾號「碼海」，可以通過以下二維碼關注。轉載本文請聯系碼海公眾號。
