leetcode_062

public class  {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        
        for(int i = 0; i < m; i++) {
            if(obstacleGrid[i][0] == 1) {
                obstacleGrid[i][0] = 0;
            } else {
                if(i-1>=0) {
                    obstacleGrid[i][0] = obstacleGrid[i-1][0];
                } else {
                    obstacleGrid[i][0] = 1;
                }
            }
        }
        
        // 第一行如果有一个点有路障，后面都是0
        // 这里可以从 1 开始
        for(int i = 1; i < n; i++) {
            if(obstacleGrid[0][i] == 1) {
                obstacleGrid[0][i] = 0;
            } else {
                    obstacleGrid[0][i] = obstacleGrid[0][i-1];
            }
        }
        
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                } else {
                	// 动态规划
                    obstacleGrid[i][j] =  obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
                }
            }
        }
        // 最后要特别判断一下
        if(obstacleGrid[m-1][n-1] == -1) {
            return 0;
        }
        return obstacleGrid[m-1][n-1];
    }
}