63.Unique Paths II:修订间差异

来自WHY42
Riguz留言 | 贡献
Riguz留言 | 贡献
第1行: 第1行:
=Description=
=Description=
{{LeetCode
|id=unique-paths-ii
|no=63
|difficulty=Medium
|category=Dynamic Programming
|collection=Top 150
|title=Unique Paths II
|summary=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:
<syntaxhighlight lang="java">
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
</syntaxhighlight>
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:
<syntaxhighlight lang="java">
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
</syntaxhighlight>


=Solution=
=Solution=

2023年9月23日 (六) 13:01的版本

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