115. Unique Paths II/63. Unique Paths II

• 本題難度: Easy/Medium
• Topic: Dynamic Programming

Description

Follow up for "Unique Paths":

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.

Example
Example 1:
Input: [[0]]
Output: 1

Example 2:
Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Explanation: Only 2 different path.

Notice
m and n will be at most 100.

我的代碼

class Solution:"""@param obstacleGrid: A list of lists of integers@return: An integer"""def uniquePathsWithObstacles(self, obstacleGrid):# write your code heren = len(obstacleGrid)m = len(obstacleGrid[0])res = [[0 for _ in range(m+1)] for _ in range(n+1)]if obstacleGrid[0][0] or obstacleGrid[-1][-1]:return 0else:res[1][1] = 1for i in range(1,n+1):for j in range(1,m+1):if j==1 and i==1:continueif obstacleGrid[i-1][j-1]==0:res[i][j]=res[i-1][j]+res[i][j-1]else:res[i][j] = 0return res[n][m]

別人的代碼

https://leetcode.com/problems/unique-paths-ii/discuss/23410/Python-different-solutions-(O(m*n)-O(n)-in-place).

# O(m*n) space def uniquePathsWithObstacles1(self, obstacleGrid):if not obstacleGrid:return r, c = len(obstacleGrid), len(obstacleGrid[0])dp = [[0 for _ in xrange(c)] for _ in xrange(r)]dp[0][0] = 1 - obstacleGrid[0][0]for i in xrange(1, r):dp[i][0] = dp[i-1][0] * (1 - obstacleGrid[i][0])for i in xrange(1, c):dp[0][i] = dp[0][i-1] * (1 - obstacleGrid[0][i])for i in xrange(1, r):for j in xrange(1, c):dp[i][j] = (dp[i][j-1] + dp[i-1][j]) * (1 - obstacleGrid[i][j])return dp[-1][-1]# O(n) space def uniquePathsWithObstacles2(self, obstacleGrid):if not obstacleGrid:return r, c = len(obstacleGrid), len(obstacleGrid[0])cur = [0] * ccur[0] = 1 - obstacleGrid[0][0]for i in xrange(1, c):cur[i] = cur[i-1] * (1 - obstacleGrid[0][i])for i in xrange(1, r):cur[0] *= (1 - obstacleGrid[i][0])for j in xrange(1, c):cur[j] = (cur[j-1] + cur[j]) * (1 - obstacleGrid[i][j])return cur[-1]# in place def uniquePathsWithObstacles(self, obstacleGrid):if not obstacleGrid:return r, c = len(obstacleGrid), len(obstacleGrid[0])obstacleGrid[0][0] = 1 - obstacleGrid[0][0]for i in xrange(1, r):obstacleGrid[i][0] = obstacleGrid[i-1][0] * (1 - obstacleGrid[i][0])for i in xrange(1, c):obstacleGrid[0][i] = obstacleGrid[0][i-1] * (1 - obstacleGrid[0][i])for i in xrange(1, r):for j in xrange(1, c):obstacleGrid[i][j] = (obstacleGrid[i-1][j] + obstacleGrid[i][j-1]) * (1 - obstacleGrid[i][j])return obstacleGrid[-1][-1]

思路
類似于62. Unique Paths
參考的代碼很好。第一是少了一個(gè)判斷條件，直接用乘以(1-obstackeGrid[][])代替，二是節(jié)約了空間

轉(zhuǎn)載于:https://www.cnblogs.com/siriusli/p/10387873.html

總結(jié)

以上是生活随笔為你收集整理的[Lintcode]115. Unique Paths II/[Leetcode]63. Unique Paths II的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。