因為它，差點無緣大廠夢！！！

2020 年 10 月 24 日
筆記

前言

今天，小萊在leetcode上閑逛，突然眼前一亮，咦！這不是去年來百度二面時的一道演算法題嗎？沒想到在這遇到了。想當時險些栽到上邊，不過最後千鈞一髮之際，還是想到了解決方法，順利拿到offer 。

畫外音：後來，在小米的面試環節中也遇到了此題。

那麼，今天小萊就給大家分享下這道動態規劃題。

題目：

一個機器人位於一個 m × n 網格的左上角（起始點在下圖中標記為「Start」）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為「Finish」）。

問總共有多少條不同的路徑？

說明：m 和 n 的值均不超過 100。

例如，上圖是一個7 × 3 的網格。有多少可能的路徑？

畫外音：Leetcode第62題，中等/難度。

不同路徑

我們由終點位置倒推，從圖中可以看出，想要到達終點，A、B兩點是必經之路。那麼，我們想要得到起點到終點的路徑數，計算出到達A、B兩點的路徑總數不就能夠得出來了嗎？但是A、B兩點的路徑數如何得出呢。

我們不妨再往前推，到達A點需要經過C或者D這兩點，到達A點的路徑數可以通過到達C、D兩點的路徑總數得知。

同樣地，到達B點需要經過D點或E點，到達B點的路徑數可以通過到達D、E兩點的路徑總數得知。

到這，聰明的你有沒有發現規律：

每一個點可到達路徑數 = 其相鄰左邊點可到達路徑數 + 其相鄰上邊點可到達路徑數

現在，我們可以回到起點了。

我們可以把m×n方格看作一個二維數組，數組中的每個元素表示：

起點到該方格的路徑數

（默念三遍！！！）

如下圖中，機器人到達第X行（僅第0行）或第Y列（僅第0列）中的任意方格都只有一條路徑。因此，我們將第X行、第Y列的方格元素都置為1。

接著，我們繼續向其它點走。現在分別經過路徑一、路徑二走到了S點，因此到達S點的路徑有2條。

最終，我們得到這樣一張網格，每個格子里記錄了起點到該格的路徑數。

但是如何用程式碼表示呢？上邊提到，我們可以將其看作一個二維數組v[m][n]。初始時，將第0行、第0列賦值為1。通過雙層循環，將目標點的上邊元素與左邊元素相加，即可得到當前路徑數。

程式碼實現：

int uniquePaths(int m, int n){
    if (m == 1 || n == 1) {
        return 1;
    }

    int i, j;
    int v[m][n];

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

    return v[m-1][n-1];
}

畫外音：本文使用C語言實現，但是不會涉及複雜的語言特性，所以無需擔心看不懂。另外，程式碼實現小萊在leetcode親測！！！

不同路徑 II

進行到這裡，我們就實現了機器人從起點到終點暢通無阻情況下所要走的路徑。

你可能注意到了，小萊重點標記了下『暢通無阻』這4個字，這說明還有存在障礙物的情況。那麼現在我們就來看看，存在障礙物的情況下，機器人所走的路徑數有多少。

畫外音：此題為Leetcode第63題，中等/難度。

如圖中，給定一個二維數組obstacleGrid[m][n]，用1來表示障礙物，用0表示空位置。

同樣地，我們還是用二維數組v[m][n]來表示機器人到達某個方格的路徑數。

但是在處理時，與無障礙物不同的是，其不再是簡單向右或向下移動。初始化和計算時要考慮障礙。

這裡分為兩種情況：

1、當障礙物出現在第0行或第0列，此時一旦遇到障礙，後續方格無法到達，因此後續行列路徑數只能為0；

畫外音：這裡只給出第0行、第0列路徑數。

2、當障礙物出現在非第0行與第0列的任意位置時，如果當前方格為障礙物時，可以直接將該方格賦值為0；

現在我們可以通過程式碼來實現了，首先初始化二維數組v[m][n]，值默認都為0。接著初始化第0行和第0列，當未遇到障礙物時路徑數為1，否則為0，其後方格的路徑也都為0。然後通過雙層循環，將目標點的上邊元素與左邊元素相加，即可得到當前路徑數（在這個過程中如果遇到障礙物的話其方格數為0）。

程式碼實現：

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    // m代表行 n代表列
    int m = obstacleGridSize, n = * obstacleGridColSize;
    if (obstacleGrid[0][0] == 1) {
        return 0;
    }

    int i, j;
    int v[m][n];
    memset(v, 0, m * n * sizeof(int));
    //初始化第一列
    for (i = 0; i < m; i++) {
        if (obstacleGrid[i][0] == 1) {
            break;
        }
        v[i][0] = 1;
    }
    //初始化第一行
    for (j = 0; j < n; j++) {
        if (obstacleGrid[0][j] == 1) {
            break;
        }
        v[0][j] = 1;
    }

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            v[i][j] = obstacleGrid[i][j] == 1 ? 0 : (v[i][j-1] + v[i-1][j]);
        }
    }

    return v[m-1][n-1];
}