63. Unique Paths II

Question

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 * 10<sup>9</sup>.

Solution

机器人只朝向一个方向移动，不存在折返。
因此可以采用动态规划，直接记录到某个点的总路线数。
当遇到障碍时（即当前访问的格子为1）则不更新dp[]数组。

Code

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        
        for(int x = 1; x < m+1; x++){
            for(int y = 1; y < n+1; y++){
                if(obstacleGrid[x-1][y-1] == 0){
                    dp[x][y] = dp[x][y-1] + dp[x-1][y];
                }
            }
        }
        return dp[m][n];
    }
}