mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
43 lines
1.6 KiB
Markdown
Executable File
43 lines
1.6 KiB
Markdown
Executable File
# [63. Unique Paths II](https://leetcode.com/problems/unique-paths-ii/)
|
||
|
||
|
||
## 题目
|
||
|
||
A robot is located at the top-left corner of a *m* x *n* grid (marked 'Start' in the diagram below).
|
||
|
||
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
|
||
|
||
Now consider if some obstacles are added to the grids. How many unique paths would there be?
|
||
|
||
|
||
|
||
An obstacle and empty space is marked as `1` and `0` respectively in the grid.
|
||
|
||
**Note:** *m* and *n* will be at most 100.
|
||
|
||
**Example 1:**
|
||
|
||
Input:
|
||
[
|
||
[0,0,0],
|
||
[0,1,0],
|
||
[0,0,0]
|
||
]
|
||
Output: 2
|
||
Explanation:
|
||
There is one obstacle in the middle of the 3x3 grid above.
|
||
There are two ways to reach the bottom-right corner:
|
||
1. Right -> Right -> Down -> Down
|
||
2. Down -> Down -> Right -> Right
|
||
|
||
## 题目大意
|
||
|
||
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
|
||
|
||
|
||
## 解题思路
|
||
|
||
- 这一题是第 62 题的加强版。也是一道考察 DP 的简单题。
|
||
- 这一题比第 62 题增加的条件是地图中会出现障碍物，障碍物的处理方法是 `dp[i][j]=0`。
|
||
- 需要注意的一种情况是，起点就是障碍物，那么这种情况直接输出 0 。
|