Commitcd4be47

authored

Merge pull requestyoungyangyang04#439 from EnzoSeason/leetcode-63

update 63. 不同路径 II：提供一维dp数组的Python解法

2 parentsa04dd4e +24e7994 commitcd4be47Copy full SHA for cd4be47

File tree

+32

-0

lines changed

+32

-0

lines changed

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -232,6 +232,38 @@ class Solution:`
`232`	`232`	`return dp[-1][-1]`
`233`	`233`	```
`234`	`234`
	`235`	+```python
	`236`	`+classSolution:`
	`237`	`+"""`
	`238`	`+ 使用一维dp数组`
	`239`	`+"""`
	`240`	`+`
	`241`	`+defuniquePathsWithObstacles(self,obstacleGrid: List[List[int]]) ->int:`
	`242`	`+ m, n=len(obstacleGrid),len(obstacleGrid[0])`
	`243`	`+`
	`244`	`+# 初始化dp数组`
	`245`	`+# 该数组缓存当前行`
	`246`	`+ curr= [0]* n`
	`247`	`+for jinrange(n):`
	`248`	`+if obstacleGrid[0][j]==1:`
	`249`	`+break`
	`250`	`+ curr[j]=1`
	`251`	`+`
	`252`	`+for iinrange(1, m):# 从第二行开始`
	`253`	`+for jinrange(n):# 从第一列开始，因为第一列可能有障碍物`
	`254`	`+# 有障碍物处无法通行，状态就设成0`
	`255`	`+if obstacleGrid[i][j]==1:`
	`256`	`+ curr[j]=0`
	`257`	`+elif j>0:`
	`258`	`+# 等价于`
	`259`	`+# dp[i][j] = dp[i - 1][j] + dp[i][j - 1]`
	`260`	`+ curr[j]= curr[j]+ curr[j-1]`
	`261`	`+# 隐含的状态更新`
	`262`	`+# dp[i][0] = dp[i - 1][0]`
	`263`	`+`
	`264`	`+return curr[n-1]`
	`265`	+```
	`266`	`+`
`235`	`267`
`236`	`268`	`Go：`
`237`	`269`

Comments

(0)