[LeetCode] 63. Unique Paths II 不同的路徑之二

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

這道題是之前那道 Unique Paths 的延伸，在路徑中加了一些障礙物，還是用動態(tài)規(guī)劃 Dynamic Programming 來解，使用一個二維的 dp 數(shù)組，大小為 (m+1) x (n+1)，這里的 dp[i][j] 表示到達(dá) (i-1, j-1) 位置的不同路徑的數(shù)量，那么i和j需要更新的范圍就是 [1, m] 和 [1, n]。狀態(tài)轉(zhuǎn)移方程跟之前那道題是一樣的，因為每個位置只能由其上面和左面的位置移動而來，所以也是由其上面和左邊的 dp 值相加來更新當(dāng)前的 dp 值，如下所示：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

這里就能看出來初始化 d p數(shù)組的大小為 (m+1) x (n+1)，是為了 handle 邊緣情況，當(dāng)i或j為0時，減1可能會出錯。當(dāng)某個位置是障礙物時，其 dp 值為0，直接跳過該位置即可。這里還需要初始化 dp 數(shù)組的某個值，使得其能正常累加。當(dāng)起點(diǎn)不是障礙物時，其 dp 值應(yīng)該為1，即dp[1][1] = 1，由于其是由 dp[0][1] + dp[1][0] 更新而來，所以二者中任意一個初始化為1即可。由于之后 LeetCode 更新了這道題的 test case，使得使用 int 型的 dp 數(shù)組會有溢出的錯誤，所以改為使用 long 型的數(shù)組來避免 overflow，代碼如下：

解法一：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<long>> dp(m + 1, vector<long>(n + 1, 0));
        dp[0][1] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (obstacleGrid[i - 1][j - 1] != 0) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};

或者我們也可以使用一維 dp 數(shù)組來解，省一些空間，參見代碼如下：

解法二：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<long> dp(n, 0);
        dp[0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) dp[j] = 0;
                else if (j > 0) dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(63.不同的路徑之二)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)不同的路徑之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論