LeetCode - Medium - 63. Unique Paths II
Topic
- Array
- Dynamic Programming
- Matrix
Description
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
Constraints:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j]
is0
or1
.
Analysis
方法一:动态规划(二维数组)(Carl教程)
方法二:动态规划(一维数组)(我写的)
Submissions
public class UniquePathsII {
//方法一:动态规划(二维数组)
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i ) {
dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j ) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i ) {
for (int j = 1; j < n; j ) {
if (obstacleGrid[i][j] == 1)
continue;
dp[i][j] = dp[i - 1][j] dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
//方法二:动态规划(一维数组)
public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[] dp = new int[n];
int firstRowBlockIndex = n, firstColBlockIndex = m;
for(int i = 0; i < m; i ) {
for(int j = 0; j < n; j ) {
if(obstacleGrid[i][j] == 1) {
if(i == 0 && firstRowBlockIndex == n) {
firstRowBlockIndex = j;
}
if(j == 0 && firstColBlockIndex == m) {
firstColBlockIndex = i;
}
dp[j] = 0;
continue;
}
if(i == 0 || j == 0) {
dp[j] = (i == 0 && j >= firstRowBlockIndex ||
j == 0 && i >= firstColBlockIndex) ? 0 : 1;
}else if(j > 0){
dp[j] = dp[j - 1];
}
}
}
return dp[n - 1];
}
}
Test
import static org.junit.Assert.*;
import org.junit.Test;
public class UniquePathsIITest {
@Test
public void test() {
UniquePathsII uObj = new UniquePathsII();
assertEquals(2, uObj.uniquePathsWithObstacles(new int[][] {{0,0,0},{0,1,0},{0,0,0}}));
assertEquals(1, uObj.uniquePathsWithObstacles(new int[][] {{0,1},{0,0}}));
assertEquals(2, uObj.uniquePathsWithObstacles2(new int[][] {{0,0,0},{0,1,0},{0,0,0}}));
assertEquals(1, uObj.uniquePathsWithObstacles2(new int[][] {{0,1},{0,0}}));
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgghjig
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13