LeetCode063——不同路径II
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/unique-paths-ii/description/
题目描述:
知识点:动态规划
思路:动态规划
和LeetCode062——不同路径一样的思路。
状态定义:f(x, y) ---------- 到达坐标(x, y)的路径数
状态转移:
(1)如果x == 0,寻找到二维数组obstacleGrid中第一行中第一个为1的元素的纵坐标记为indexj。那么
a.当y < indexj时,f(0, y) = 1。
b.当y >= indexj时,f(0, y) = 0。
(2)如果y == 0,寻找到二维数组obstacleGrid中第一列中第一个为1的元素的横坐标记为indexi。那么
a.当x < indexi时,f(x, 0) = 1。
b.当x >= indexi时,f(x, 0) = 0。
(3)否则,
a.当obstacleGrid[x, y] == 1时,f(x, y) = 0。
b.当obstacleGrid[x, y] != 1时,f(x, y) = f(x - 1, y) + f(x, y - 1)。
时间复杂度和空间复杂度均为O(m * n),其中m为obstacleGrid数组的行数,n为obstacleGrid数组的列数。
JAVA代码:
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
if(m == 0) {
return 0;
}
int n = obstacleGrid[0].length;
int[][] map = new int[m][n];
int indexj = 0;
for (; indexj < n; indexj++) {
if(obstacleGrid[0][indexj] == 1) {
break;
}
}
for (int i = 0; i < indexj; i++) {
map[0][i] = 1;
}
int indexi = 0;
for (; indexi < m; indexi++) {
if(obstacleGrid[indexi][0] == 1) {
break;
}
}
for (int i = 0; i < indexi; i++) {
map[i][0] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 1) {
map[i][j] = 0;
}else {
map[i][j] = map[i - 1][j] + map[i][j - 1];
}
}
}
return map[m - 1][n - 1];
}
}
LeetCode解题报告: