63.Unique Paths II

Description

	#63	Unique Paths II	Medium
		Dynamic Programming	Top 150
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Solution

2D DP

Runtime 1ms		Memory 40.02MB

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];
    }
}