美文网首页
回溯vs记忆化递归 2020-11-01(未允禁转)

回溯vs记忆化递归 2020-11-01(未允禁转)

作者: 9_SooHyun | 来源:发表于2020-11-01 23:04 被阅读0次

    本文再谈一谈回溯和记忆化递归的差别

    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]
    

    相关文章

      网友评论

          本文标题:回溯vs记忆化递归 2020-11-01(未允禁转)

          本文链接:https://www.haomeiwen.com/subject/fsguvktx.html