Commitabccf35

authored

Merge pull requestyoungyangyang04#458 from EnzoSeason/leetcode-115

update115: 使用一维dp数组，并剪枝

2 parentsaf3c7af +6f7a254 commitabccf35Copy full SHA for abccf35

File tree

+34

-0

lines changed

+34

-0

lines changed

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -186,6 +186,40 @@ class Solution:`
`186`	`186`	`return dp[-1][-1]`
`187`	`187`	```
`188`	`188`
	`189`	`+Python3:`
	`190`	+```python
	`191`	`+classSolutionDP2:`
	`192`	`+"""`
	`193`	`+ 既然dp[i]只用到dp[i - 1]的状态，`
	`194`	`+ 我们可以通过缓存dp[i - 1]的状态来对dp进行压缩，`
	`195`	`+ 减少空间复杂度。`
	`196`	`+ （原理等同同于滚动数组）`
	`197`	`+"""`
	`198`	`+`
	`199`	`+defnumDistinct(self,s:str,t:str) ->int:`
	`200`	`+ n1, n2=len(s),len(t)`
	`201`	`+if n1< n2:`
	`202`	`+return0`
	`203`	`+`
	`204`	`+ dp= [0for _inrange(n2+1)]`
	`205`	`+ dp[0]=1`
	`206`	`+`
	`207`	`+for iinrange(1, n1+1):`
	`208`	`+# 必须深拷贝`
	`209`	`+# 不然prev[i]和dp[i]是同一个地址的引用`
	`210`	`+ prev= dp.copy()`
	`211`	`+# 剪枝，保证s的长度大于等于t`
	`212`	`+# 因为对于任意i，i > n1, dp[i] = 0`
	`213`	`+# 没必要跟新状态。`
	`214`	`+ end= iif i< n2else n2`
	`215`	`+for jinrange(1, end+1):`
	`216`	`+if s[i-1]== t[j-1]:`
	`217`	`+ dp[j]= prev[j-1]+ prev[j]`
	`218`	`+else:`
	`219`	`+ dp[j]= prev[j]`
	`220`	`+return dp[-1]`
	`221`	+```
	`222`	`+`
`189`	`223`	`Go：`
`190`	`224`
`191`	`225`

Comments

(0)