63.不同路径 II (Medium)*

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