LeetCode-63-Unique Paths Ⅱ

这道题Unique Path的续集。

题意:输入一个二维数组,这个二维数组的元素如果是0,表示对应网格处没有障碍,可以正常向下或向右移动;如果这个数字是1,表示对应网格处有个障碍,机器人🤖将不能通过。

思路:
(1)首先我们考虑一下特殊情况。如果第一个网格或最后一个网格对应的数字为1,那么意味着是不可达的,因此直接返回0即可。
(2)排除掉这两种情况后,我们还是先生成一个二维数组 dp,dp[i][j]表示走到图中第 i 行第 j 列个网格点共有多少种走法。首先考虑第一行。如果某个位置的 obstacle[0][j] = 1,那么这个网格点以及它右面和它下面的其他网格点都无法到达,因此我们需要一个标记 flag 来表示是否遇到了 obstacle = 1的情况。如果 flag = true,那么dp[0][j] = 1。只有当 flag != true && obstacle[0][j] != 1 时,有 dp[0][j] = 1。第一列也是类似的。
(3)然后考虑第 i 行第 j 列的网格点。对于 dp[i][j] 来说,如果 obstacle[i][j] = 0,那么 dp[i][j] = dp[i-1][j] + dp[i][j-1];如果obstacle[i][j] = 1,那么 dp[i][j] = 0。这就是该题的状态转移方程。

代码如下:

发表评论

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