63.Unique Paths II - 版本历史

Riguz：/* 2D DP */

2023-09-23T13:05:28Z

2D DP

←上一版本		2023年9月23日 (六) 13:05的版本
第34行：		第34行：
	=Solution=		=Solution=
	== 2D DP==		== 2D DP==
	{{Submission\|runtime=~~1ms~~\|memory=40.~~02MB~~\|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;
	}		}

Riguz：/* Description */

2023-09-23T13:01:06Z

Description

←上一版本		2023年9月23日 (六) 13:01的版本
第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=

Riguz：/* 2D DP */

2023-09-23T12:59:38Z

2D DP

←上一版本		2023年9月23日 (六) 12:59的版本
第3行：		第3行：
	=Solution=		=Solution=
	== 2D DP==		== 2D DP==
	{{Submission\|runtime=1ms\|memory=44.~~49MB~~\|rp=19.16\|mp=98.98}}		{{Submission\|runtime=1ms\|memory=40.02MB\|rp=19.16\|mp=98.98}}
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	class Solution {		class Solution {

Riguz：/* 2D DP */

2023-09-23T12:58:56Z

2D DP

←上一版本		2023年9月23日 (六) 12:58的版本
第38行：		第38行：
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			[[Category:Algorithm]]
			[[Category:Dynamic Programming]]
			[[Category:LeetCode]]

Riguz：Created page with "=Description= =Solution= == 2D DP== {{Submission|runtime=1ms|memory=44.49MB|rp=19.16|mp=98.98}} 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..."

2023-09-23T12:58:41Z

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..."

新页面

=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(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];
}
}
</syntaxhighlight>

63.Unique Paths II - 版本历史

Riguz：​/* 2D DP */

Riguz：​/* Description */

Riguz：​/* 2D DP */

Riguz：​/* 2D DP */

Riguz：/* 2D DP */

Riguz：/* Description */

Riguz：/* 2D DP */

Riguz：/* 2D DP */