63.不同的路径II

不是很难。
初始化时想了想
在转移时要判断当前有没有障碍物，有的话就是0；没有的话才可以路径相加。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int dp[][]=new int[obstacleGrid.length][obstacleGrid[0].length];
        if(obstacleGrid[0][0]==0) dp[0][0]=1;
        for(int i=1;i<obstacleGrid.length;i++){
            if(obstacleGrid[i][0]==0) dp[i][0]=dp[i-1][0];
            else dp[i][0]=0;
        }
        for(int i=1;i<obstacleGrid[0].length;i++){

            if(obstacleGrid[0][i]==0) dp[0][i]=dp[0][i-1];
            else dp[0][i]=0;
        }
        for(int i=1;i<obstacleGrid.length;i++){
            for(int j=1;j<obstacleGrid[0].length;j++){
                if(obstacleGrid[i][j]==0) dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
}

---

原来也能在原数组上进行，这样空间复杂度变为了O(1)了