LeetCode 063 Unique Paths II

LeetCode

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 space is marked as 1 and 0 respectively in the grid.

Example 1:

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:

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.

题目大意：

求矩阵路径总数。有障碍

解题思路：

求个数用DP，递归式：

1 2	dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacle[i][j-1] == 0 = 0 if obstacle[i][j-1] == 1

解题步骤：

N/A

注意事项：

obstacleGrid[i][j-1], j-1因为dp从1开始, 但i不是，因为dp不含i。

Python代码：

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
	dp = [0] * (len(obstacleGrid[0]) + 1)
	dp[1] = 1
	for i in range(len(obstacleGrid)):
		for j in range(1, len(dp)):
			if obstacleGrid[i][j - 1] == 0:
				dp[j] += dp[j - 1]
			else:
				dp[j] = 0
	return dp[-1]

算法分析：

时间复杂度为O(n²)，空间复杂度O(n²)