LC 63 Unique Paths II(M)

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid.

边界判断：同 LeetCode 62

解题思路：

• 当(m==0 || n==0)路径始终为1， 因为不能左或上， 其他情况

  u(m, n) = u(m-1, n) + u(m, n-1);

  当遇到当前obstacleGrid[row][col]是 1 的时候 所有过这里的路径无效，u(m, n) = 0;

这里使用一种优化，用一个行数组保存 当前行的路径数，

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length<1)
            return 0;
        int width = obstacleGrid[0].length;
        int[] dp= new int[width];
        dp[0] = 1; //initial first value
        for(int row = 0; row< obstacleGrid.length; row++){//process row
            for(int col = 0; col < width; col++){
                if(obstacleGrid[row][col]==1){
                    dp[col] = 0;
                }else{
                    if(col > 0){
                        dp[col] = dp[col] + dp[col -1]; // Translate to dp[oldTop]+ dp[curLeft];
                    }
                }
            }
        }
        return dp[width - 1];
    }