LeetCode 90 Unique Paths II

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.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.
분석:
전체적인 사고방식은 Unique Paths와 마찬가지로 장애물이 존재하기 때문에 판단 논리를 많이 해야 한다. 장애물이 있는 것은 0이면 된다.
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null || obstacleGrid.length==0 || obstacleGrid[0].length==0)
            return 0;
        int m = obstracleGrid.length;
        int n = onstracleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = 1;//           
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){//j 0         
                if(obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else if(j>0)
                    dp[j] = dp[j-1]+dp[j];
            }
        }
        return dp[n-1];
    }
}

좋은 웹페이지 즐겨찾기