63.Unique Paths II：修订间差异
| （未显示同一用户的2个中间版本） | |||
| 第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= | {{Submission|runtime=0ms|memory=40.48MB|rp=100|mp=68}} | ||
<syntaxhighlight lang="java"> | <syntaxhighlight lang="java"> | ||
class Solution { | class Solution { | ||
public int uniquePathsWithObstacles(int[][] grid) { | |||
int rows = grid.length, cols = grid[0].length; | |||
int[][] dp = new int[rows][cols]; | |||
public int uniquePathsWithObstacles(int[][] | |||
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; | dp[i][j] = 0; | ||
else if( i == rows -1 && j == cols -1) | else if( i == rows -1 && j == cols -1) | ||
dp[i][j] = 1; | 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]; | ways += dp[i+1][j]; | ||
if(j < cols -1) | if(j < cols -1) | ||
ways += dp[i][j+1]; | ways += dp[i][j+1]; | ||
dp[i][j] = ways; | dp[i][j] = ways; | ||
} | } | ||
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];
}
}