本文再谈一谈回溯和记忆化递归的差别
1.回溯vs记忆化递归
- 1.从思考问题的角度看,
使用回溯法解决问题,不涉及【不断递减问题规模至出口case】,而就是直直白白地解一整个问题;使用记忆化递归,则不断递减问题规模至出口case,解决当前问题等价于解决若干个子问题 - 2.从返回值看,
回溯无返回值,只负责在回溯树的叶子结点处将合法的结果纳入结果集,然后return;记忆化递归必须有返回值,当前问题的解需要依赖子问题的解,因此需要将子问题的解返回 - 3.从时间复杂度看,
使用回溯法解决问题,要获取完整的解集,代码每次都得走到回溯树的叶子结点,然后将走过的路径纳入结果集,可能部分路径之前已经走过了,也仍然不可避免地需要重复再走来获得一整条完整路径,因此,【回溯是无法保存中间状态的,要获得每一个解就必须次次走到叶子结点】,时间复杂度较高O(N!);使用记忆化递归,则可以保存中间状态,减少重复计算,时间复杂度可以优化。另外,这也可以从两种方法的返回值差异来解释:回溯函数无返回值,只负责叶子的结果结算,记录不了回溯树每一个中间结点的状态,所以走过回溯树的每一个结点都不会留下足迹,下次来到同一结点就像没有来过一样还得往下走;记忆化递归有返回值,即子问题都有对应的解,因此可以将计算过的子问题结果保存起来,减少重复计算
2.对比小结
回溯:整体解决一个问题,函数无返回值,无法储存中间结果
记忆化递归:解决一个问题=解决其子问题,函数有返回值,可以储存中间结果
而记忆化递归的逆向过程就是dp动规,显然,记忆化递归和dp是更优的方法,而回溯妥妥的就是暴力
3.例
leetcode140. 单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
示例 1:
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
思路
1.回溯思路:将字典中的每一个word与s的前缀匹配,能够匹配则更新单词路径,并截取新的s通过dfs重复以上的操作。思路没错,但时间复杂度高会超时
# 回溯
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
res = []
# 递归的dfs回溯
def dfs(s, wordDict, temp_res):
nonlocal res
# 递归出口
if not s:
res.append(' '.join(temp_res))
return
# 递归
for word in wordDict:
l = len(word)
if s[:l] == word:
# 修改状态
temp_res.append(word)
# dfs
dfs(s[l:], wordDict, temp_res)
# 状态恢复
temp_res.pop()
dfs(s, wordDict, [])
return res
2.记忆化递归:定义函数dfs(s, wordDict),返回值List[str]表示s的解析结果,出口s == ''或s在字典self.d内,通过记忆中间结果避免重复计算,通过
class Solution:
def __init__(self):
self.d = dict()
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
# 返回值List[str], 出口s == ''或s在字典self.d内
def dfs(s, wordDict):
# 返回[]说明不可解析,返回['']说明可解析
res = []
# 出口
if not s:
return ['']
if s not in self.d:
# 比对每个单词是否匹配s的前缀,匹配则可缩小问题规模
for word in wordDict:
l = len(word)
if s[:l] == word:
ans = dfs(s[l:], wordDict)
# 递归式
if ans:
for sentence in ans:
res.append(word+ ' ' + sentence)
self.d[s] = res
return self.d[s]
result = dfs(s, wordDict)
# 去掉最后一个空格符
return [s[:-1] for s in result]
网友评论