63.Unique Paths II

Solution

2D DP

Runtime 1ms		Memory 44.49MB

class Solution {
    private int[][] grid;
    private int rows;
    private int cols;
    private int[][] dp;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        this.grid = obstacleGrid;
        this.rows = obstacleGrid.length;
        this.cols = obstacleGrid[0].length;
        this.dp = new int[rows][cols];
        for(int[] temp: dp) 
            Arrays.fill(temp, -1);
        for(int i = rows - 1; i >=0; i--) {
            for(int j = cols -1; j >= 0; j--) {
                if(grid[i][j] == 1)
                    dp[i][j] = 0;    // obstacle
                else if( i == rows -1 && j == cols -1)
                    dp[i][j] = 1;    // reach end
                else {
                    int ways = 0;
                    if(i < rows -1).
                        ways += dp[i+1][j];  // going down
                    if(j < cols -1)
                        ways += dp[i][j+1];  // going right
                    dp[i][j] = ways;
                }
            }
        }
        return dp[0][0];
    }
}