[[340340]]

前言

動態(tài)規(guī)劃的算法題經(jīng)常出現(xiàn)在大廠的面試中，它是非常適合考查候選人的一類題型，因為它難度適中，需要一定的技巧，而且根據(jù)習(xí)題可以有一定的變化，所以如果想去大廠，建議大家好好刷一下此類題目，接下來我會寫一些動態(tài)規(guī)劃的相關(guān)題解，希望能對大家理解此類習(xí)題有所幫助。

今天我們來看一道騰訊面試題，題目如下:

有如下 8 x 8 格子，機器人需要從入口走到出口,每次只能朝右或朝下走，粉色格子為障礙物，機器人不能穿過，問機器人從入口走到出口最少需要的步數(shù)是多少?

題解分析

這道題其實我們之前在前文解析過類似的題目，只不過當(dāng)時求的是從入口到出口最多共有多少種走法，而本題稍微變化了一下，求的是最少需要的步數(shù)。整體思路其實是一樣的，大家可以先看看前文，思考一下，然后再看看我的題解。

首先最容易想到的當(dāng)然是暴力解法，對于機器人來說，每一步都可以向下或向右走

所以我們可以用暴力算法求出所有路徑所需求步數(shù)，然后求其最小步數(shù)，偽代碼如下

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

時間復(fù)雜度是多少?對于機器人所處的每一個格子來說，下一步可以走兩步(向右或向下)，共有 N 個格子，所以共有 O(2^n) 步可走，指數(shù)級別!暴力解法顯然有很大的問題。

這道題其實考察的是用動態(tài)規(guī)劃的思想來求解。

動態(tài)規(guī)劃主要解題思路是用自底向上的思想來求解，求入口到出口的最短路徑叫自頂向上，而求出口到入口的最短路徑即為自底向上。怎么求，我們先看下出口的上一個位置。

對這個位置來說，它往出口走只需要一步，所以我們在它的位置上填1，同理，它的上一個位置必須經(jīng)由此位置走到出口，所以它的上一個位置應(yīng)該填 2，依此類推，我們可以在右邊填上這些格子走到出口的步數(shù)

同理可得底部的格子到出口的位置，如下:

可能有人會說了，如果右邊和底邊有個格子有障礙物咋辦，如下

對于這種情況，由于障礙物上面的格子不可能通向出口，所以障礙物上面的格子應(yīng)該填無窮大(另外，顯而易見，所有障礙物本身所在格子應(yīng)該填無窮大)，如下

以上最右列和最底邊格子所填數(shù)字即為動態(tài)規(guī)劃的 base case，求完了 base case，還要得出動態(tài)規(guī)劃的「狀態(tài)轉(zhuǎn)移方程」，得出狀態(tài)轉(zhuǎn)移方程后，動態(tài)規(guī)劃求解基本上就大功告成了，一起來看下怎么求解。

現(xiàn)在我們再從右到左，從下到上依次遍歷每個格子，求出每個格子到出口的最小步數(shù)，我們知道每個格子的下一步只能向右或向下，所以每個格子到出口的最小步數(shù)可按如下公式求解

當(dāng)前格子到出口的最小步數(shù) = 1 + min(右格子到出口最小步數(shù)，下方格子到出口的最小步數(shù))

此公式即為狀態(tài)轉(zhuǎn)移方程

舉個例子，以下方的 A，B 兩個格子為例

對于 A 格子來說，它的右格子，下方格子到出口的最小步數(shù)是 1，所以其到出口的最小步數(shù)為 1+min(1,1) = 2。

對于 B 來說，它右格子到出口的最小步數(shù)為 3，其下格子是障礙物，到出口的步數(shù)為無窮大，所以 B 到出口的最小步數(shù)為 1 + min(∞, 3) = 4。如下

依此類推，我們可以得出每個格子到出口的最小步數(shù)，如下所示：

填滿之后到了入口位置，顯然入口到出口的最少步數(shù)應(yīng)該是 1 + min(13，13) = 14 步。以下是代碼，注釋寫得很清楚了，相信大家應(yīng)該能看懂。

public class Solution { 
 
    /** 
     * 初始化格子,假設(shè)為 8 x 8， -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 getMinStep() { 
        /** 
         * 格子為 8 x 8 
         */ 
        int N = 8; 
 
        // 如果格子為障礙物，則此格子到出口的距離標(biāo)記為無究大（這里用100000表示），代表此格子到出口不通 
        Integer infinity = 100000; 
 
        /** 
         * 初始化最右邊的格子,從最后一列的倒數(shù)第二行開始（因為最后一個格子為出口） 
         */ 
        for (int row = N-2; row >= 0; row--) { 
            // 如果當(dāng)前格子的下一個格子不是障礙物，則當(dāng)前格子到出口的最小步數(shù)為 1 + 下個格子到出口的步數(shù) 
            if (GRIDS[row+1][N-1] != -1) { 
                GRIDS[row][N-1] = 1 + GRIDS[row+1][N-1]; 
            } else { 
                // 如果下一個格子是障礙物，則此格子到出口的步數(shù)設(shè)置為無窮大（代表此路不通），這里用正整數(shù)的最大值表示 
                GRIDS[row][N-1] = infinity; 
            } 
        } 
 
        /** 
         * 初始化最底部的格子,從最后一行的倒數(shù)第二列開始（因為最后一個格子為出口） 
         */ 
        for (int column = N-2; column >= 0; column--) { 
            // 如果當(dāng)前格子右邊的格子不是障礙物，則當(dāng)前格子到出口的最小步數(shù)為 1 + 右格子到出口的步數(shù) 
            if (GRIDS[N-1][column+1] != -1) { 
                GRIDS[N-1][column] = 1 + GRIDS[N-1][column+1]; 
            } else { 
                // 如果是障礙物，則到出口的步數(shù)為無窮大，這里用正整數(shù)的最大值表示 
                GRIDS[N-1][column] = infinity; 
            } 
        } 
 
        /** 
         * 從右到左，從下到上填滿每個格子的值，由于最右和最底部的格子都初始化了， 
         * 所以從倒數(shù)第二行，倒數(shù)第二列開始遍歷 
         */ 
        for (int i = N - 2; i >= 0; i--) { 
            for (int j = N - 2; j >= 0; j--) { 
                // 說明是障礙物，所在格子到出口步數(shù)顯然為無窮大（代表此路不通） 
                if (GRIDS[i][j] == -1) { 
                    GRIDS[i][j] = infinity; 
                    continue; 
                } 
                /** 
                 * 當(dāng)前格子到出口的最小步數(shù)為1+(右邊的格子到出口的步數(shù)與下格子到出口步數(shù)之和的最小值) 
                 */ 
                GRIDS[i][j] = 1 + Math.min(GRIDS[i+1][j], GRIDS[i][j+1]); 
            } 
        } 
 
        /** 
         * 遍歷完之后起點格子對應(yīng)的值即為最終所求的解 
         */ 
        return GRIDS[0][0]; 
    } 
 
    public static void main(String[] args) { 
        int result = Solution.getMinStep(); 
        System.out.println("result = " + result); 
    } 
} 

理清了思路，剩下用代碼實現(xiàn)就相對簡單了，接下來我們分析下時間復(fù)雜度和空間復(fù)雜度。

時間復(fù)雜度中間有兩層循環(huán)，所以顯然為 O(N^2)，空間復(fù)雜度呢，我們并沒有分配額外的空間來存儲數(shù)據(jù)，而是復(fù)用了代表迷宮的格子數(shù)組 GRIDS，所以空間復(fù)雜度為 O(1)。有人可能會問了，為啥可以直接用 GRIDS 來計算格子到出口的步數(shù)，這樣不就把格子的信息(如是否是障礙物)給覆蓋了嗎。這里就要了解一下動態(tài)規(guī)劃的無后效性了，啥叫無后效性。

以上文所舉例子為例，對于圖中的 A，B 格子來說，由狀態(tài)轉(zhuǎn)移方程

當(dāng)前格子到出口的最小步數(shù) = 1 + min(右格子到出口最小步數(shù)，下方格子到出口的最小步數(shù)) 

可知，計算它到出口的最短步數(shù)只與它的右格子與下方格子到出口的最小步數(shù)有關(guān)(此時右格子與下方格子的步數(shù)已經(jīng)計算出來)也就是說對于 A，B 格子來說，它只關(guān)心它的右格子與下方格子中的步數(shù)，至于這兩個格子的步數(shù)是如何算出來的，它們不關(guān)心，這就叫無后效性。

所以我們可以從右到左，從下到上依次遍歷每個格子的步數(shù)，將其填入 GRIDS 中，這樣雖然 GRIDS 中的格子信息被覆蓋了，但對計算被遍歷到的格子到出口的步數(shù)沒有影響。巧妙使用無后效性在很多場景下可以有效壓縮空間，降低空間復(fù)雜度。

本文轉(zhuǎn)載自微信公眾號「碼?！?，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼海公眾號。