63.Unique Paths II:修订间差异

来自WHY42
Riguz留言 | 贡献
Created page with "=Description= =Solution= == 2D DP== {{Submission|runtime=1ms|memory=44.49MB|rp=19.16|mp=98.98}} <syntaxhighlight lang="java"> 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(in..."
 
Riguz留言 | 贡献
 
(未显示同一用户的3个中间版本)
第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=
== 2D DP==
== 2D DP==
{{Submission|runtime=1ms|memory=44.49MB|rp=19.16|mp=98.98}}
{{Submission|runtime=0ms|memory=40.48MB|rp=100|mp=68}}
<syntaxhighlight lang="java">
<syntaxhighlight lang="java">
class Solution {
class Solution {
    private int[][] grid;
     public int uniquePathsWithObstacles(int[][] grid) {
    private int rows;
         int rows = grid.length, cols = grid[0].length;
    private int cols;
         int[][] dp = new int[rows][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 i = rows - 1; i >=0; i--) {
             for(int j = cols -1; j >= 0; j--) {
             for(int j = cols -1; j >= 0; j--) {
                 if(grid[i][j] == 1)
                 if(grid[i][j] == 1)
                     dp[i][j] = 0;   // obstacle
                     dp[i][j] = 0;
                 else if( i == rows -1 && j == cols -1)
                 else if( i == rows -1 && j == cols -1)
                     dp[i][j] = 1;   // reach end
                     dp[i][j] = 1;
                 else {
                 else {
                     int ways = 0;
                     int ways = 0;
                     if(i < rows -1).
                     if(i < rows -1)
                         ways += dp[i+1][j]; // going down
                         ways += dp[i+1][j];
                     if(j < cols -1)
                     if(j < cols -1)
                         ways += dp[i][j+1]; // going right
                         ways += dp[i][j+1];
                     dp[i][j] = ways;
                     dp[i][j] = ways;
                 }
                 }
第38行: 第60行:
}
}
</syntaxhighlight>
</syntaxhighlight>
[[Category:Algorithm]]
[[Category:Dynamic Programming]]
[[Category:LeetCode]]

2023年9月23日 (六) 13:05的最新版本

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 0ms
Memory 40.48MB
class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        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;
                else if( i == rows -1 && j == cols -1)
                    dp[i][j] = 1;
                else {
                    int ways = 0;
                    if(i < rows -1)
                        ways += dp[i+1][j];
                    if(j < cols -1)
                        ways += dp[i][j+1];
                    dp[i][j] = ways;
                }
            }
        }
        return dp[0][0];
    }
}