63.-unique-paths-ii.md

63. Unique Paths II

{% tabs %} {% tab title="CPP" %}

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& A) {
        if (A.size() == 0 || A[0].size() == 0) return 0;
        int m = A.size();
        int n = A[0].size();
        vector<vector<int>> dp(m, vector<int>(n,0));
        for (int i = 0; i < m ; i++){
            if (A[i][0] == 1) break;
            else{
                dp[i][0] = 1;
            } 
        }
        for (int j = 0; j < n ; j++){
            if (A[0][j] == 1) break;
            else{
                dp[0][j] = 1;
            } 
        }
        
        for (int i = 1; i < m ; i++){
            for (int j = 1; j < n ; j ++){
                if (A[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];
    }
};

{% endtab %}

{% tab title="Python" %}

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid or obstacleGrid[0][0] == 1:
            return 0
        dp = [[0] * len(obstacleGrid[0]) for _ in range(len(obstacleGrid))]
        dp[0][0] = 1
        for i in range(len(obstacleGrid)):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1
            else:
                break
        for j in range(len(obstacleGrid[0])):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break
                
        for i in range(1,len(obstacleGrid)):
            for j in range (1,len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = 0
        # print(dp)
        
        return dp[-1][-1]

{% endtab %}

{% tab title="优化" %}

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        if obstacleGrid[0][0] == 0:
            dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 0:
                    if i == j == 0:
                        continue
                    else:
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

{% endtab %} {% endtabs %}