Commit81e31c3

committed

added O(min(m,n)) solution to Unique paths

1 parent9dd9c1d commit81e31c3Copy full SHA for 81e31c3

File tree

+17

-1

lines changed

+17

-1

lines changed

Lines changed: 17 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,9 +1,25 @@`
`1`	`1`	`classSolution:`
	`2`	`+`
`2`	`3`	`defuniquePaths(self,m,n):`
`3`	`4`	`ways= [[1]foriinrange(m)]`
`4`	`5`	`foriinrange(1,n):`
`5`	`6`	`ways[0].append(1)`
`6`	`7`	`foriinrange(1,m):`
`7`	`8`	`forjinrange(1,n):`
`8`	`9`	`ways[i].append(ways[i-1][j]+ways[i][j-1])`
`9`		`-returnways[m-1][n-1]`
	`10`	`+returnways[m-1][n-1]`
	`11`	`+`
	`12`	`+# it's pascal's triangle, we can get result by computing C(m,n), we can`
	`13`	`+# achieve O(min(m,n))`
	`14`	`+`
	`15`	`+defuniquePaths_2(self,m,n):`
	`16`	`+ifm<n:`
	`17`	`+returnself.uniquePaths(n,m)`
	`18`	`+ifm==1andn==1:`
	`19`	`+return1`
	`20`	`+m,n,res=m+n-2,n-1,1`
	`21`	`+ifn> (m/2):`
	`22`	`+n=m-n`
	`23`	`+foriinxrange(n):`
	`24`	`+res=res* (m-i)/ (i+1)`
	`25`	`+returnres`

Comments

(0)