63. Unique Paths II 「不同路径 II」

一个机器人站立在 m×n 方格的左上角(下图中标记为“Start”的位置)。

这个机器人只能向右或向下移动。机器人正在试着移动到方格的右下角(下图中标记为“Finish”的位置)。

如果方格中有一些障碍物,那么共有多少条不同的路径可以移动?

方格中障碍物用 1 表示,0 表示没有障碍物。

提示: mn 最大为 100。

例一:
输入: [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
输出: 2
解释:
在 3×3 的方格中存在一个障碍物。
这里有两条路径可以到达右下角:
1. 右->右->下->下
2. 下->下->右->右

这个题和上一个题很像,同样是求路径的数量,不过这次在某些位置可能会出现障碍物,导致机器人不能通过。

如果这个障碍物只出现一次的话,那么就又是一个经典的数理统计问题,相信学过高中数学或者高数的同学都做过这种题。

在这个问题中,障碍物可能会出现多次,使用我们熟悉的数学方法就不太适合这个问题了。这次我们仍然使用动态规划来解决。

我们首先考虑第一行的情况,当第一行的某一位置有障碍物时,则其路径数量为 0,而没有障碍物时,其路径数量等于其左边位置路径数量 10。接着是考虑第一列的情况,情况和第一行类似,当第一列的某一位置有障碍物i时,其路径数量为 0,而没有障碍物时,其路径数量等于其上边位置路径数量 10

这里说一下第一行第一列的位置,如果其有障碍物,我们就可以不用计算了,直接返回 0 就行。同理如果最后一行最后一列有障碍物,同样返回 0。第一个位置在没有障碍物的时候我们就可以将其路径数量设置为 1,然后再进入循环逐行检查。

在检查时,每一位置的路径数量等于 其上方位置的路径其左方位置的路径 的和,遇到障碍物时直接将其值设为 0 即可。

/*
 * 63. Unique Paths II
 * https://leetcode.com/problems/unique-paths-ii/
 * https://www.whosneo.com/63-unique-paths-ii/
 */

public class UniquePathsWithObstacles {
    public static void main(String[] args) {
        UniquePathsWithObstacles solution = new UniquePathsWithObstacles();

        int[][] grid = new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };

        System.out.println(solution.uniquePathsWithObstacles(grid));
    }

    private int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
            return 0;

        // 每一位置的移动路径的数量等于
        // 其上方位置的路径 与 其左方位置的路径 的和
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (i == 0 && j == 0)
                    obstacleGrid[i][j] = 1;
                else if (i == 0) // 第一行
                    obstacleGrid[0][j] = obstacleGrid[0][j] == 0 ? obstacleGrid[0][j - 1] : 0;
                else if (j == 0) // 第一列
                    obstacleGrid[i][0] = obstacleGrid[i][0] == 0 ? obstacleGrid[i - 1][0] : 0;
                else
                    obstacleGrid[i][j] = obstacleGrid[i][j] == 0 ? obstacleGrid[i][j - 1] + obstacleGrid[i - 1][j] : 0;

        return obstacleGrid[m - 1][n - 1];
    }

    private int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
            return 0;

        // 用一个更大的数组来存储结果,这样就无需考虑第一行或第一列的情况
        int[][] result = new int[m + 1][n + 1];
        result[1][1] = 1;

        for (int i = 1; i < m + 1; i++)
            for (int j = 1; j < n + 1; j++)
                if (i >1 || j > 1)
                    result[i][j] = obstacleGrid[i - 1][j - 1] == 0 ? result[i][j - 1] + result[i - 1][j] : 0;

        return result[m][n];
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注