题目要求
机器人走迷宫，在一个m*n的迷宫中从左上方走到左下方，问能走多少条路，或者是在迷宫中设置了障碍物表示此路不同，此时会有一个障碍矩阵obstacle[m][n]其中0表示无障碍物，1表示有障碍物，求问有多少条路径,如下图中所示：
image
解题方法
- 解析方法按照有障碍物的情况进行分析解答，无障碍物的情况直接退化即可，采用动态规划或者回溯法可解。（本题采用动态规划）
- 思路如下：
- 要到达右下方最后一格其路径数记为F(m, n),此时根据要求可解出最优子结构：F(m, n) = F(m-1, n) + F(m, n-1);
- 其边界条件为第一行和第一列的值，此时因为有obstacle这个矩阵那么根据obstacle矩阵确定第一行和第一列的值分为两种情况（以第一行为例），如果obstacle[0][i] = 1; 那么result[0][i] = 0, 否则 result[0][i] = result[0][i-1];(i从1到n-1)
- 状态转移公式：F(x, y) = F(x-1, y) + F(x, y-1), obstacle(x,y)=0;(x,y >= 1) 否则 F(x, y) = 0,obstacle(x, y) = 0;
- 根据以上所述，采用一个二维矩阵，由上至下合并的方法即可生成最终的结果，首先将边界条件确定再使用状态转移公式。
迷宫代码如下中所示
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid.length == 0) return 0;
//动态规划
int[][] result = new int[obstacleGrid.length][obstacleGrid[0].length];
if (obstacleGrid[0][0] == 0) result[0][0] = 1;
else result[0][0] = 0;
//将第一行的边界条件填满
for (int i = 1; i < result[0].length; i++) {
if (obstacleGrid[0][i] == 0) {
result[0][i] = result[0][i-1];
} else result[0][i] = 0;
}
//将第一列边界填满
for (int i = 1; i < result.length; i++) {
if (obstacleGrid[i][0] == 0) {
result[i][0] = result[i-1][0];
} else result[i][0] = 0;
}
//动态执行
for (int i = 1; i < result.length; i++) {
for (int j = 1; j < result[0].length; j++) {
if (obstacleGrid[i][j] == 0) {
result[i][j] = result[i-1][j] + result[i][j-1];
} else result[i][j] = 0;
}
}
return result[result.length-1][result[0].length-1];
}
}
无障碍物密码如下中所示
class Solution {
public int uniquePaths(int m, int n) {
if (m == 0 && n == 0) return 0;
if (m == 1 || n == 1) return 1;
int[][] result = new int[m][n];
for (int i = 0; i < n; i++) {
result[0][i] = 1;
}
for (int i = 0; i < m; i++) {
result[i][0] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
result[i][j] = result[i-1][j] + result[i][j-1];
}
}
return result[m-1][n-1];
}
}
个人博客链接
动态规划初级说明
http://www.waiqiang.ren/2018/11/04/%E4%BB%80%E4%B9%88%E6%98%AF%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/
