AI summary
type
status
date
slug
summary
category
tags
icon
password
之前 二叉树系列算法核心纲领 把递归穷举划分为「遍历」和「分解问题」两种思路，其中「遍历」的思路扩展延伸一下就是 回溯算法，「分解问题」的思路可以扩展成 动态规划算法。
这种思维转换不止局限于二叉树相关的算法，本文就跳出二叉树类型问题，来看看实际算法题中如何把问题抽象成树形结构，见招拆招逐步优化，从而进行「遍历」和「分解问题」的思维转换，从回溯算法顺滑地切换到动态规划算法。
先说句题外话，前文说，标准的动态规划问题一定是求最值的，因为动态规划类型问题有一个性质叫做「最优子结构」，即从子问题的最优解推导出原问题的最优解。
但在我们平常的语境中，就算不是求最值的题目，只要看见使用备忘录消除重叠子问题，我们一般都称它为动态规划算法。严格来讲这是不符合动态规划问题的定义的，说这种解法叫做「带备忘录的 DFS 算法」可能更准确些。不过咱也不用太纠结这种名词层面的细节，既然大家叫的顺口，就叫它动态规划也无妨。
本文讲解的两道题目也不是求最值的，但依然会把他们的解法称为动态规划解法，这里提前跟大家说下这个变通，免得严谨的读者疑惑。其他不多说了，直接看题目吧。

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
这是一道非常高频的面试题，我们来思考下如何通过「遍历」和「分解问题」的思路来解决它。

遍历的思路（回溯解法）

先说说「遍历」的思路，也就是用回溯算法解决本题。回溯算法最经典的应用就是排列组合相关的问题了，不难发现这道题换个说法也可以变成一个排列问题：
现在给你一个不包含重复单词的单词列表 wordDict 和一个字符串 s，请你判断是否可以从 wordDict 中选出若干单词的排列（可以重复挑选）构成字符串 s。
这就是前文 回溯算法秒杀所有排列/组合/子集问题 中讲到的最后一种变体：元素无重可复选的排列问题，前文我写了一个 permuteRepeat 函数，代码如下：
给这个函数输入 nums = [1,2,3]，输出是 3^3 = 27 种可能的组合。
类比一下，本文讲的这道题也有异曲同工之妙，假设 wordDict = ["a", "aa", "ab"], s = "aaab"，想用 wordDict 中的单词拼出 s，其实也面对着类似的一棵 M 叉树，M 为 wordDict 中单词的个数，你需要做的就是站在回溯树的每个节点上，看看哪个单词能够匹配 s[i..] 的前缀，从而判断应该往哪条树枝上走：
notion image
回溯算法解法代码如下：
这段代码就是严格按照回溯算法框架写出来的，应该不难理解，但这段代码无法通过所有测试用例，我们来分析一下它的时间复杂度。
递归函数的时间复杂度的粗略估算方法就是用递归函数调用次数（递归树的节点数） x 递归函数本身的复杂度。对于这道题来说，递归树最多有 个节点。设 wordDict 的长度为 M，字符串 s 的长度为 N，那么回溯函数的最坏时间复杂度是 （for 循环 O(M)，字符串切片 O(N)），所以总的时间复杂度是 。
这里顺便说一个细节优化，其实你也可以反过来，通过穷举 s[i..] 的前缀去判断 wordDict 中是否有对应的单词：
这段代码和刚才那段代码的结果是一样的，但这段代码的时间复杂度变成了 ，和刚才的代码不同。根据题目给的数据范围，这段代码的实际运行效率应该稍微高一些，这个是一个细节的优化，你可以自己做一下，我就不写了。
不过即便你优化这段代码，总的时间复杂度依然是指数级的，是无法通过所有测试用例的，那么问题出在哪里呢？
比如输入 wordDict = ["a", "aa", "b"], s = "aaab"，你注意回溯算法穷举时会存在重复的情况：
notion image
图中标红的这两部分，虽然经历了不同的切分，但是切分得出的结果是相同的 "aab"，所以这两个节点下面的子树也是重复的，即存在冗余计算，这也是这个算法复杂度为指数级别的原因。

利用后序位置优化

不管是什么算法，消除冗余计算的方法就是加备忘录。回溯算法也可以加备忘录，我们可以称之为「剪枝」，即把冗余的子树给它剪掉。
就比如面对这个 "aab" 子串的局面，我希望让备忘录告诉我，这个 "aab" 到底能不能被成功切分？如果之前尝试过不能切分的话，我就直接跳过，不用遍历子树去穷举切分了，从而优化效率。如果之前尝试过能成功切分的话，就结束了（这种情况已经剪枝过了，因为 found == true 本身就是个 base case，整个递归都会被终止）。
要想让备忘录做到这一点，需要在后序位置上更新备忘录，因为这个 "aab" 其实是一棵子树，对吧？你需要在遍历完子树的时候，在备忘录中记录下该子树是否可以被成功切分。
回溯函数 backtrack 为遍历而生，本身没有返回值，即没有从子树传递回来的信息。但针对这道题，我们还是有办法的，因为这不是有个外部变量 found 吗？这个变量就可以告诉我们子树是否能够成功切分：
如果 found 为 false，说明还没找到一个成功的切分，也就间接说明当前子树不能成功切分。此时我们可以在备忘录里面记一笔，从而消除掉冗余的穷举。
具体到代码上，只需稍加修改，即可实现备忘录功能：
这一版代码已经可以 AC 了。

分解问题的思路（动态规划）

上面能用回溯算法解决这个问题，其实还是这道题比较简单，我们可以借助 found 变量在后序位置更新备忘录，你会看到后面讲的单词拆分 II 就不能这么搞了。
要在后序位置更新备忘录存储子树的答案，一般还是要借助递归函数的返回值，因此还是要用「分解问题」的思维模式。
我们刚才以排列组合的视角思考这个问题，现在我们换一种视角，思考一下是否能够把原问题分解成规模更小，结构相同的子问题，然后通过子问题的结果计算原问题的结果。
对于输入的字符串 s，如果我能够从单词列表 wordDict 中找到一个单词匹配 s 的前缀 s[0..k]，那么只要我能拼出 s[k+1..]，就一定能拼出整个 s。换句话说，我把规模较大的原问题 wordBreak(s[0..]) 分解成了规模较小的子问题 wordBreak(s[k+1..])，然后通过子问题的解反推出原问题的解。
有了这个思路就可以定义一个 dp 函数：
对于这个 dp 函数，指针 i 的位置就是「状态」，所以我们可以通过添加备忘录的方式优化效率，避免对相同的子问题进行冗余计算。最终的解法代码如下：
还可以再优化。
注意到计算 prefix 的过程中，我们是直接调用编程语言提供的子串截取函数，这个函数的时间复杂度是 O(N)。不难发现截取子串的开始索引是固定的 i，结束索引是递增的 j，所以我们手动维护这个 prefix 子串，避免调用子串截取函数，进一步提高效率。这个小优化就留给你来做吧。
我们来算一下它的时间复杂度。因为有备忘录的辅助，消除了递归树上的重复节点，使得递归函数的调用次数从指数级别降低为状态的个数 O(N)，函数本身的复杂度还是 ，所以总的时间复杂度是 。

140. 单词拆分 II

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意：词典中的同一个单词可能在分段中被重复使用多次。
相较上一题，这道题不是单单问你 s 是否能被拼出，还要问你是怎么拼的，其实只要把之前的解法稍微改一改就可以解决这道题。

回溯

上一道题的回溯算法维护一个 found 变量，只要找到一种拼接方案就提前结束遍历回溯树，那么在这道题中我们不要提前结束遍历，并把所有可行的拼接方案收集起来就能得到答案：

后序位置优化

对于重复的子树，依然会造成没有必要的重复遍历，我们依然可以通过备忘录的方式进行优化，即可以在备忘录缓存子串 "aab" 的切分结果，避免重复遍历相同的子树。
但用回溯算法就不好加备忘录了，因为回溯算法的 track 变量仅维护了从根节点到当前节点走过的路径，并没有记录子树的信息。
所以，这种题目想要消除重叠子问题的话一般要用分解问题的思路，利用函数返回值来更新备忘录。

动态规划

这个问题也可以用分解问题的思维解决，把上一道题的 dp 函数稍作修改即可：
为什么返回 [""] 而不是 []？
  • 如果返回 []，表示“没有合法的拆分方式”，上一层递归就不会继续拼接。
  • 但我们其实是“已经拆完了”，所以要返回一个“空的句子”，表示“后面没有内容了”。