63.Unique Paths II === ###### tags: `Medium`,`Array`,`DP` [63. Unique Paths II](https://leetcode.com/problems/unique-paths-ii/) ### 題目描述 You are given an `m x n` integer array `grid`. There is a robot initially located at the **top-left corner** (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time. An obstacle and space are marked as `1` or `0` respectively in `grid`. A path that the robot takes cannot include **any** square that is an obstacle. Return *the number of possible unique paths that the robot can take to reach the bottom-right corner.* The testcases are generated so that the answer will be less than or equal to 2 * 10^9^. ### 範例 **Example 1:** ![](https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg) ``` Input: obstacleGrid = [[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 ``` **Example 2:** ![](https://assets.leetcode.com/uploads/2020/11/04/robot2.jpg) ``` Input: obstacleGrid = [[0,1],[0,0]] Output: 1 ``` **Constraints**: * `m` == `obstacleGrid.length` * `n` == `obstacleGrid[i].length` * 1 <= `m`, `n` <= 100 * `obstacleGrid[i][j]` is `0` or `1`. ### 解答 #### Python ```python= class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [[0] * (n + 1) for _ in range(m + 1)] dp[0][1] = 1 for i in range(m): for j in range(n): dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] if obstacleGrid[i][j] == 0 else 0 return dp[-1][-1] ``` > [name=Yen-Chi Chen][time=Sun, Aug 13, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)