LeetCode_63. 不同路徑 II

題目描述：

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中标記為“Start” ）。

機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為“Finish”）。

現在考慮網格中有障礙物。那麼從左上角到右下角将會有多少條不同的路徑？

網格中的障礙物和空位置分别用 1 和 0 來表示。

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

示例 1:

輸入:

[

[0,0,0],

[0,1,0],

[0,0,0]

]

輸出: 2

解釋:

3x3 網格的正中間有一個障礙物。

從左上角到右下角一共有 2 條不同的路徑：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<long>> dp(m,vector<long>(n));//這裡需要是用long型，不然dp[i][j]=dp[i-1][j]+dp[i][j-1]會超出int的範圍
        if(obstacleGrid[0][0]==1)//起點處有障礙物,則不存在路徑
            return 0;
        dp[0][0]=1;
        //下面的兩個for循環是初始化第一行和第一列的數值
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0];
            if(obstacleGrid[i][0]==1)
                dp[i][0]=0;
        }
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1];
            if(obstacleGrid[0][i]==1)
                dp[0][i]=0;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==1)
                    dp[i][j]=0;
                else
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};