题目要求

机器人走迷宫，在一个m*n的迷宫中从左上方走到左下方，问能走多少条路，或者是在迷宫中设置了障碍物表示此路不同，此时会有一个障碍矩阵obstacle[m][n]其中0表示无障碍物，1表示有障碍物，求问有多少条路径,如下图中所示：

解题方法

1. 解析方法按照有障碍物的情况进行分析解答，无障碍物的情况直接退化即可，采用动态规划或者回溯法可解。（本题采用动态规划）
2. 思路如下：
   • 要到达右下方最后一格其路径数记为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;
3. 根据以上所述，采用一个二维矩阵，由上至下合并的方法即可生成最终的结果，首先将边界条件确定再使用状态转移公式。

迷宫代码如下中所示

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/

动态规划初级说明

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/