C++怎么解決不同的路徑問題

今天小編給大家分享一下C++怎么解決不同的路徑問題的相關(guān)知識點，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

不同的路徑

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)起點不是障礙物時，其 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];
    }
};

以上就是“C++怎么解決不同的路徑問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。