Leetcode Unique Path II

题意

给定一个m*n的矩阵，从右上走到右下，记1为blocker无法通行。问有多少条不同的path

题目链接

https://leetcode.com/problems/unique-paths-ii/description/

题解

可以用dp，dp[i]][j]代表对于走到坐标(i, j)有多少条不同的path，注意初始化的时候第0行和第0列，如果有blocker，那么从当前石头开始，当前行或者列都没有

代码

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

时间复杂度: $O(mn)$
空间复杂度：$O(mn)$