63. 不同路径 II
程序员文章站
2022-07-16 12:04:17
...
难度:中等
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用
1
和0
来表示。说明:m 和 n 的值均不超过 100。
示例 1:
输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有2条不同的路径: 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
分析:
题目中说只能往下或往右移动,那么,回推一步的机器人必然在当前位置的上方(up)或者左边(left)一格,到达当前位置的路径数为达到上方位置和左边位置的加和,即path_now = path_up + path_left。
这就是一道典型的动态规划。
另外需要注意的是,障碍物(1)所在位置的path值为0,因为不可到达。最上方一行和最左边一列的path_now值只取决于前一个位置的path值,可放在最前面先行遍历。
代码:
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
//存放到当前位置的路径数
int[][] path = new int[m][n];
if(obstacleGrid[0][0]==1)
path[0][0]=0;
else path[0][0]=1;
//初始化最顶和最左的数据
for (int i = 1; i < m; i++) {
if(obstacleGrid[i][0]==1)
path[i][0]=0;
else
path[i][0]=path[i-1][0];
}
for (int i = 1; i < n; i++) {
if(obstacleGrid[0][i]==1)
path[0][i]=0;
else
path[0][i]=path[0][i-1];
}
//填充后续path数据
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if(obstacleGrid[i][j]==1)
path[i][j]=0;
else path[i][j]=path[i-1][j]+path[i][j-1];
}
}
return path[m-1][n-1];
}
}
结果:
下一篇: 洛谷P1094 纪念品分组(Java)