63. 不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // dp[i][j] 到达坐标ij的不同路径树
        // dp[i][j] = obstacleGrid[i][j]==1?0:(i>0?dp[i-1][j]:0)+(j>0?dp[i][j-1]:0);
        int m=obstacleGrid.size();int n=obstacleGrid[0].size();
        vector<vector<int>>dp(m, vector<int>(n,0));
        int cnt = 1;
        for(int j=0;j<n;j++){
            if (obstacleGrid[0][j]==1)cnt = 0;
            dp[0][j]=cnt;
        }
        for(int i=1;i<m;i++)for(int j=0;j<n;j++){
            dp[i][j] = obstacleGrid[i][j]==1?0:(i>0?dp[i-1][j]:0)+(j>0?dp[i][j-1]:0);
        }
        return dp[m-1][n-1];
    }
};