简介
笔者最近在和同事准备校招题的时候，有一道涉及到回溯的编程题，发现自己也不会，看了答案也没什么感觉，因此收集材料整理下。
本文涉及到两道题目：
- 利用字符‘a’、‘b’ 、 ‘c’ 、‘d’ 、‘e’ 、‘f’、‘g’生成并输出所有可能的字符串（但字符不可重复使用，输出顺序无要求），比如： “a”、“b”、“c”、“d”、“e”、“f”、“g”、“ab”、“ba”、“ac”、“ca”
- 集合A的幂集是由集合A的所有子集所组成的的集合，如：
A=1，2，3，则A的幂集P（A）={1，2，3}，{1，2}，{1，3}，{1}，{2，3}，{2}，{3}，{ }，求一个集合的幂集就是求一个集合的所有的子集。来自回溯法求幂集
两个问题基本一样，主要是回溯法求幂集 对回溯法的一些思路表述的比较精彩。下文会混用两个问题。
重新理解递归
写递归函数的正确思维方法基本要点：
- 递归算法采用的是分治的思想，把一个大问题分解为若干个相似的子问题求解。
- 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中（把变量的变化依次写出来）， 因为回溯就像反过来思考迭代，这是我们习惯的思维方式， 但是其实无益于理解。数学归纳法才是理解的递归的方式，函数式编程也有这么点意思。
- 递归并不是算法，它是和迭代对应的⼀种编程⽅法。只不过，我们通常借 助递归去分解问题⽽已。对于
f(n) = max(f(n-1),f(n-2))可以用递归写，也可以用 用迭代 从f(0) f(1) 一直求到f(n)，迭代的空间复杂度更低一些。递归就是自我调用，经常作为一种编程的实现方式，DFS 、动态规划、回溯法都可以用递归来实现，当然也可以用非递归来实现。 - 如果你刚开始接触递归，⼀个简 单练习递归的⽅式是将你写的迭代全部改成递归形式。⽐如你写了⼀个程 序，功能是“将⼀个字符串逆序输出”，那么使⽤迭代将其写出来会⾮常容 易，那么你是否可以使⽤递归写出来呢？通过这样的练习，可以让你逐步 适应使⽤递归来写程序。
基本思路
- 定义递归函数功能。尤其是参数和返回值的选择，dfs 下传哪些信息（参数或全局变量）以便子节点做判断：有几个分叉，是否可以终止，如何剪枝。
- 找出递归结束的条件。当我们处理递归问题时， 如何定义递归出口是非常重要的一步。递归出口是递归函数 可以直接处理的最简单子问题。请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。或者说，只要你觉得参数是什么时，你能够直接知道函数的结果，那么你就可以把这个参数作为结束的条件。一把有关树的DFS 问题，递归出口都是叶子节点或空节点，然后基于叶子节点/空节点 判断当前路径是否符合要求。
- 找出函数的等价关系式。我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。
递归中如果存在重复计算（称为重叠⼦问题），那就是使 ⽤记忆化递归（或动态规划）解题的强有⼒信号之⼀。可以看出动态规划 的核⼼就是使⽤记忆化的⼿段消除重复⼦问题的计算，如果这种重复⼦问 题的规模是指数或者更⾼规模，那么记忆化递归（或动态规划）带来的收 益会⾮常⼤。为了消除这种重复计算，我们可使⽤查表的⽅式。即⼀边递归⼀边使⽤ “记录表”（⽐如哈希表或者数组）记录我们已经计算过的情况，当下次再 次碰到的时候，如果之前已经计算了，那么直接返回即可，这样就避免了 重复计算。
回溯法
回溯法是一种复杂度很高的暴力搜索算法 ，时间复杂度是O(2^n)。 不同于普通的暴力搜索，回溯法会在每一步判断状态是否合法，而不是等到状态全部生成后再进行确认。当某一步状态非法时，它将回退到上一步中正确的位置，然后继续搜索其它不同的状态。前进和后腿是回溯法的关键动作，因此可以使用一个递归函数去模拟整个搜索过程，即使用递归实现回溯法。很多时候每一步的处理都是一致的，这时候用递归来实现就很自然。
回溯法采⽤ 试错 的思想，它尝试分步的去解 决⼀个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上⼀步甚⾄是上⼏步的计 算，再通过其它的可能的分步解答再次尝试寻找问题的答案。 通俗上讲，回溯是⼀种⾛不通就回头的算法。回溯算法强调了「深度优先遍历」思想的用途，当回溯用于树的时候，就是深度优先搜索DFS，借助系统栈空间，保存所需要的状态变量。当然了，几乎所有可以用回溯解决的问题都可以表示为（要学会用树辅助分析）。那么这俩在这里就几乎同义了。
回溯的本质是穷举所有可能，尽管有时候可以通过剪枝去除⼀些根本不可 能是答案的分⽀， 但是从本质上讲，仍然是⼀种暴⼒枚举算法。回溯法可以抽象为树形结构，并且是是⼀颗⾼度有限的树（N 叉树）。回溯法解决的都是在集合中查找⼦集，集合的⼤⼩就是树的叉数，递归的深 度，构成树的⾼度。
PS：与dp 类似， 回溯也是有方向的，对于字符串、数组问题，有时候是从前向后回溯，有时候则是从后向前回溯（比如连续字串问题，从前向后 不能继续推导的）。
算法模板
// 有时候仅仅是向下层传递 i 是不够的，还应透传更多状态，下传哪些信息以便子节点做决策？终止条件、分支个数等
const visited = {} // 记录访问过的路径，回溯发标配
function dfs(i) { // i 表示当前走到哪里了
if (满⾜特定条件）{ // 找到可行解提前结束搜索；搜索完毕，已经没有可搜索的解空间
// 返回结果 or 退出搜索空间
}
visited[i] = true // 将当前状态标为已搜索
dosomething(i) // 对当前节点i做⼀些操作
for (根据i能到达的下个状态j) { // for 循环⽤来枚举分割点
if (!visited[j]) { // 如果状态j没有被搜索过
dfs(j)
}
}
undo(i) // 恢复i
}
除了业务有特性可以利用外，回溯树一般前进到 叶子的左右（都是nil）孩子才会终止，需要注意：
function dfs(root *TreeNode) xx {
if root == nil { // 终止条件
// 此时要注意的是，叶子的left right 都为nil ，都会执行到这里，会被执行两次
return xx
}
// 对当前node 进行处理
}
回溯的本质就是暴⼒枚举所有可能。要注意的是，由于回溯通常结果集都 记录在回溯树的路径上，因此如果不进⾏撤销操作， 则可能在回溯后状 态不正确导致结果有差异， 因此需要在递归到底部往上冒泡的时候进⾏ 撤销状态。
回溯题⽬的⼀个考点是剪枝， 通过恰当地剪枝，可以有效减少时 间，剪枝在每道题的技巧都是不⼀样的
- ⼀个简单的原则就是避免根本不可能是答案的递归。
- 根据问题的特性，调整分叉的顺序，使得每次尝试的“路径”都是概率最大的，以便尽早结束对当前节点其它分叉的遍历，但因为问题的特性很难全部掌握，概率最大的分叉也有失败的可能，所以会有“回溯”的动作。
动态规划
如果求从一个tree 从root 到所有leaf 路径的最大和（每一个node 有一个int），只能用回溯法（此时的回溯只是遍历树的手段），说白了就是遍历所有路径，路径没有遍历完，不能确定哪个最大。但是求一个矩阵从左上角到右下角 所有可选路径（假设只能向右或向下）哪个最大，则可以使用动态规划，因为到达右下角之前，一定会到达“右下角” 上边或左边的点。
为什么动态规划会快一点
动态规划和其它算法思想如递归、回溯、分治、贪心等方法都有一定的联系，其背后的基本思想是枚举，虽然看起来简单， 但如何涵盖所有可能，并尽可能重叠子问题的计算是一个难点。与回溯法的暴力枚举不同（刷leetocode，很多题上来就用递归做肯定能做出来，但超时了），动态规划法的枚举是没有重复的，这种不重复建立在巧妙的利用之前计算过的结果集上。然而想利用之前计算过的结果集，就需要对问题进行分解，因此动态规划法都会涉及对原问题进行分解的过程。大致上， 若要解决一个给定问题， 我们需要解决其各个部分（即子问题），再根据子问题的解得出原问题的解。
- 动态规划的本质是将大问题转化为小问题，并且大问题的解和小问题是有关联的。
- 动态规划算的本质使用空间换时间，通过计算和记录状态来得到最优解。其实大部分动态规划问题都是“选择”和“不选择”的问题，比如背包问题就是“装”还是“不装”，选择的标准就是看哪种选择带来的价值更大，因此我们要做的就是对于选择和不选择两种情况分别求值，然后取最大者。比如爬楼梯问题，
dp[i] = dp[i-1] + dp[i-2]，此处的i 是越来越大， 最终目的是计算f(n)；也有的i 是越来越小，最终目的是计算dp[0]。转换公式本质是一种对遍历的加速，也就是dp[i]需要一个复杂的公式算一下，现在直接可以通过dp[i-1]和dp[i-2]计算而来。回溯法因为每次只考虑当前路径，面对“选择”，只能先选一条路走到底。而动态规划，是在dp[i-1]和dp[i-2]的基础上决定dp[i]，选择的背景信息已经确定了，做决定即可。 - 因为大部分动态规划问题都是“选择”和“不选择”的问题，所以这些问题一般无法用o(n)方法解决。因此o(n) 只遍历一遍，如果根据当前状态 （最多加上之前遍历得到的一些信息）无法做出选择，就只能求助于o(nlogn) 或o(n^2) 算法了。
状态压缩解法：我们要用动态规划的思路来解决这个问题，就不能脱离状态和决策。状态是我们之前遍历过的位置的状态，加上当前所处的地点，这两者的结合。状态确定了，决策就很简单了，凡是当前地点能去的之前没有去过的位置，都可以构成决策，能采取的决策是有限制的。在动态规划问题当中，复杂度等于状态数乘上决策数。
定义状态
⽆后效性决定了是否可使⽤动态规划来解决。李煜东著《算法竞赛进阶指南》，摘录如下：：为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。
- 换句话说：如果之前的阶段求解的子问题的结果包含了一些不确定的信息，导致了后面的阶段求解的子问题无法得到，或者很难得到，这叫「有后效性」。PS：子问题之间无法建立联系，求f(n) 时f(n-1) 用不上。
- 解决「有后效性」的办法是固定住需要分类讨论的地方，记录下更多的结果。在代码层面上表现为：
- 状态数组增加维度，例如：「力扣」的股票系列问题；
- 把状态定义得更细致、准确，例如：前天推送的第 124 题：状态定义只解决路径来自左右子树的其中一个子树。
动态规划的中⼼点是什么？那就是定义状态。定义好了状态，就可以画出递归 树，聚焦最优⼦结构写转移⽅程就好了，因此我才说状态定义是动态规划 的核⼼，动态规划问题的状态确实不容易看出。⽐如⼀个字符串的状态，通常是 dp[i]表示字符串 s 以 i 结尾的 ….。 ⽐如两个字符串的状态，通常是 dp[i][j] 表 示字符串 s1 以 i 结尾，s2 以 j 结尾的 ….。
每一个动态规划问题，都可以被抽象为一个数学函数，这个函数的自变量集合就是题目的所有取值，值域就是题目要求的答案的所有可能。我们的目的就是填充这个函数的内容，使得给定自变量x 能够唯一映射到一个值y。当然自变量可能有多个，要求是能将所有“选择”都描述到（动态规划就是不断在状态间做选择），最终x 的某个边界值就是我们要的解。
经典动态规划问题（理解「无后效性」）设计状态思路：把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成了复杂的问题的解。比如“最大子序列和问题”，我们 不知道和最大的连续子数组一定会选哪一个数，那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。
例如，示例 1 输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ，我们可以求出以下子问题：
- 子问题 1：经过 -2 的连续子数组的最大和是多少；
- 子问题 2：经过 1 的连续子数组的最大和是多少；
- 子问题 3：经过 -3 的连续子数组的最大和是多少；
- 子问题 4：经过 4 的连续子数组的最大和是多少；
- 子问题 5：经过 -1 的连续子数组的最大和是多少；
- 子问题 6：经过 2 的连续子数组的最大和是多少；
- 子问题 7：经过 1 的连续子数组的最大和是多少；
- 子问题 8：经过 −5 的连续子数组的最大和是多少；
- 子问题 9：经过 4 的连续子数组的最大和是多少。
一共 9 个子问题，这些子问题之间的联系并没有那么好看出来，这是因为 子问题的描述还有不确定的地方。这件事情叫做「有后效性」
例如「子问题 3」：经过 -3的连续子数组的最大和是多少。「经过 -3 的连续子数组」我们任意举出几个：
[-2,1,-3,4] ，-3 是这个连续子数组的第 3 个元素； [1,-3,4,-1] ，-3 是这个连续子数组的第 2 个元素； ……
我们不确定的是：−3 是连续子数组的第几个元素。那么我们就把 −3 定义成连续子数组的最后一个元素。在新的定义下，我们列出子问题如下：
- 子问题 1：以 -2 结尾的连续子数组的最大和是多少；
- 子问题 2：以 1 结尾的连续子数组的最大和是多少；
- 子问题 3：以 −3 结尾的连续子数组的最大和是多少；
- 子问题 4：以 4 结尾的连续子数组的最大和是多少；
- 子问题 5：以 −1 结尾的连续子数组的最大和是多少；
- 子问题 6：以 2 结尾的连续子数组的最大和是多少；
- 子问题 7：以 1 结尾的连续子数组的最大和是多少；
- 子问题 8：以 −5 结尾的连续子数组的最大和是多少；
- 子问题 9：以 4 结尾的连续子数组的最大和是多少。
我们加上了「结尾的」，这些子问题之间就有了联系。我们单独看子问题 1 和子问题 2：
子问题 1：以 −2 结尾的连续子数组的最大和是多少；
以 −2 结尾的连续子数组是 [-2]，因此最大和就是 −2。
子问题 2：以 1 结尾的连续子数组的最大和是多少；
以 1 结尾的连续子数组有 [-2,1] 和 [1] ，其中 [-2,1] 就是在「子问题 1」的后面加上 1 得到。-2 + 1 = -1 < 1 ，因此「子问题 2」 的答案是 1。
因为我们把子问题定义的更清楚，子问题之间的联系就容易观察到。这是我们定义子问题、定义状态的经验。解决「有后效性」的办法是固定住需要分类讨论的地方，记录下更多的结果。在代码层面上表现为：
- 状态数组增加维度，例如：「力扣」的股票系列问题；
- 把状态定义得更细致、准确，例如：前天推送的第 124 题：状态定义只解决路径来自左右子树的其中一个子树。
注意：此时最后一个状态值只表示以 nums[len - 1] 结尾的子数组和，状态数组 dp 的最大值才是题目要求的结果。
简单的动态规划问题，很有可能问的问题就可以设计成为子问题，复杂的动态规划问题就没有那么容易看出子问题应该如何设计了，这需要一定的解决问题的经验。
另一种定义状态的经验：动态规划问题都可以用回溯法求解（动态规划也是一种暴力枚举，只不过加速了枚举过程），回溯法经常可以使用记忆化递归优化性能，递归时一般要向下层递归函数传递当前状态，这个状态就是 状态转移方程用到的状态。PS：解题时，如果实在想不明白动态规划，可以使用记忆化递归求解。
- 一个自变量对应一维dp，两个自变量对应二维dp（三维dp 一般碰不到，碰到了直接放弃吧）。从另一个角度说，用一维dp解决的 可以用两个一维dp解决，也可以用二维dp解决，比如一些子序列问题dp[i] 等同于dp[0][i]，但如果没有 dp[i][j] 与 dp[i+1][j-1] 的关系的话（从中间推两端），用一维dp 就ok了。
- 二维dp 两个自变量有时候表示 字符串的首尾，但有时候从问题中抽取，比如背包问题，
dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少）。⽐如两个字符串的状态，通常是 dp[i][j] 表 示字符串 s1 以 i 结尾，s2 以 j 结尾的 - 动态规划时间复杂度经常无法优化了（毕竟遍历dp是省不了的），有时候可以从状态数组 dp入手 优化空间复杂度，比如将二维dp 优化为两个一维dp，甚至优化为一个一维dp（比如01背包问题）。
- 最神奇的一个搞法：记录一个数组 部分元素和，假设数组长度为n，用一个 0~n-1 位来表示 数组的某个元素是否被选中，
S=01001表示 数组第2 和第5个元素被选中，dp[S] 记录此时的结果。
有时dp 数组最后一个值（比如dp[len-1]）不一定是答案，答案可能是dp[0]（打家劫舍问题），dp 数组的最大值或最小值（乘积最大子数组）。有的时候只需要返回dp的值即可（比如返回最长xx的长度），但有时也要返回“最长xx”本身，此时dp 值可能是布尔值，最后结果可以是 j-i 的最大值。
状态转移
当你定义好了状态，剩下就三件事了：
- 临界条件； 比如⼀个⼈爬楼梯，每次只能爬 1 个或 2 个台阶，假设有 n 个台阶，那么这 个⼈有多少种不同的爬楼梯⽅法？如果我们⽤ f(n) 表示爬 n 级台阶有多少种⽅ 法的话，f(1) 与 f(2) 就是【边界】，
f(n) = f(n-1) + f(n-2)/dp[i] = dp[i-1] + dp[i-2]就是【状态转移公式】。 - 状态转移⽅程；动态规划中当前阶段的状态往往是上⼀阶段状态和上⼀阶段决策的结果。也就是说，如果给定了第 k 阶段的状态 s[k] 以及决策 choice(s[k])，则第k+1 阶段的状态 s[k+1] 也就完全确定，⽤公式表示就是：
s[k] +choice(s[k]) -> s[k+1]， 这就是状态转移⽅程。需要注意的是 choice 可能 有多个，因此每个阶段的状态 s[k+1]也会有多个。通过状态转移方程减小问题规模。
- 枚举状态。 推导公式估计看一遍就记下来了，但难就难在如何初始化和遍历顺序上。一些场景下，遍历顺序取决于状态转移⽅程：正推、反推。⽐如下面代码 我们就需要从左到右遍历，原因很简单，因为
dp[i]依赖于dp[i - 1]， 因此计算dp[i]的时候，dp[i - 1]需要已经计算好了。for i in range(1, n + 1): dp[i] = dp[i - 1] + 1
状态转移方程不一定都是dp[i]和dp[i-1]的方程（实质跟枚举类似），尤其是对于一些不连续的问题，dp[i]和dp[i-1]不一定能建立直接的推导关系，有时候dp[i] = max(dp[0]..dp[i-1])，有时候dp[i] = dp[j] && judge(i,j) 等等。PS：想不出来，就老老实实用回溯吧
更一般的说，状态转移方程是 建立 dp[i] 与dp[j] 的关系（j 满足一定条件），以便根据 dp[j] 计算 dp[i]。此时出现了一个需要解决的问题，如何保证在处理到位置 i 时，所有满足条件的位置 j 都已经被处理过了呢？
- 如果j 在i 的一侧，可以根据位置从小到大或者从大到小进行动态规划
- 如果j 分布在位置 i 的两侧，可以借助记忆化搜索的方法，即当我们需要
dp[j]的值时，如果我们之前已经计算过，就直接返回这个值（记忆）；如果我们之前没有计算过，就先将dp[i]搁在一边，转而去计算dp[j]（搜索），当dp[j]计算完成后，再用其对dp[i]进行状态转移。
如果从 状态转移方程的视角 看动态规划，状态转移方程也要在 for 循环里，也是迭代，只是迭代公式更复杂。
- 线性动态规划，
s[k] +choice(s[k]) -> s[k+1] - 区间动态规划，
f(i,j)=max{f(i,k)+f(k+1,j)+cost}
递归/回溯/动态规划对比
dfs 带不带返回值
有两种习惯
- dfs 只负责遍历，树的分叉几乎都会遍历，路径信息（比如path 新增元素与删除）代表了遍历的路径， 基本逻辑：状态扩充 + dfs 下探 + 状态回退，然后考虑 在回溯的模板上 加上 对当前节点/当前已遍历路径 的处理。谈不上什么回溯 或没有回溯，直到递归终止，此时得到了一个完整的路径，计算最大值、最小值、记录所有可行解。前序遍历。
- 通过返回值 感知到 子节点/子问题的结果。PS：其实这个返回值如果 不使用的话，就跟第一种情况一样了。后序遍历。
- 一种场景：尽早结束对当前节点其它分叉的遍历。前提是 子节点根据 下传给递归函数的信息 或全局信息 或仅凭自己的信息 就可以判断出子问题的结果。一般在递归 终止条件的地方，此时得到了一个完整的路径（如果有的话），判断当前路径是否满足解的要求（比如路径上所有节点的和为target）。继而父节点拿到子节点的返回值，判断是否还有执行下一个分叉的必要。
- 一种场景，解决问题本来就是要求 从下到上的 先拿到子节点的结果，比如求树上所有节点的和。
- 中间状态的记录，可以通过全局变量（一般对应数组这种情况，go slice 值传递会丢失自动扩容后指针），也可以都通过 递归参数传递
- 典型问题如“基于数组 nums=
[2,3,1]构造一个小于n=23231的最大数”，答案为23222。PS：第一次碰到的时候，没有想过这是一个dfs问题- 暴力 遍历数组的所有子序列（长度为5，元素可重复），用一个全局变量max记录 小于n的最大值。不遍历完，max 就可能不对。一点剪枝都没有，也不回溯（碰到不可能的解也会一条道走到黑）。
- 针对暴力法，可以优化的点是，每个分叉其实 就三个可能：和当前位相等的，仅小于当前位的，0（也就是当前位不选）。后两种其实是一种情况：选择的位数小于当前位/不相等，一旦小于当前位，后面的位全部以最大值填充即可。如果前面的位数 与n 都相等，但nums 中没有比当前位小的元素，则此路不通，回溯树回退。核心是 通过删掉不可能的分叉，调整树的分叉顺序，使得越靠前的“路径”越有可能是最终解。
以爬楼梯为例比较递归和动态规划
⼀个⼈爬楼梯，每次只能爬 1 个或 2 个台阶，假设有 n 个台阶，那么这 个⼈有多少种不同的爬楼梯⽅法？思路： 由于第 n 级台阶⼀定是从 n - 1 级台阶或者 n - 2 级台阶来的，因此到第 n级台阶的数⽬就是 到第 n - 1 级台阶的数⽬加上到第 n - 1 级台阶的数 ⽬ 。
爬楼梯问题的递归写法
function dp(n) {
if (n === 1) return 1;
if (n === 2) return 2;
return dp(n - 1) + dp(n - 2);
}
爬楼梯问题的动态规划写法，查表，即db table(dynamic_programming)，⼀般我们写的 dp table，数组的索引通常对应记忆化递归的函数参数， 值对应递归函数的返回值。
function climbStairs(n) {
if (n == 1) return 1;
const dp = new Array(n);
dp[0] = 1;
dp[1] = 2;
for (let i = 2; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[dp.length - 1];
}
滚动数组优化。爬楼梯我们并没有必要使⽤⼀维数组，⽽是借助两个变量来实现的，空间 复杂度是 O(1)
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2;
let a = 1;
let b = 2;
let temp;
for (let i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
他们的区别只不过是递归⽤调⽤栈枚举状态， ⽽动态规划使⽤迭 代枚举状态。如果说递归是从问题的结果倒推，直到问题的规模缩⼩到寻常。 那么动态规划就是从寻常⼊⼿， 逐步扩⼤规模到最优⼦结构。动态规划性能通常更好。 ⼀⽅⾯是递归的栈开销，⼀⽅⾯是滚动数 组的技巧。PS： 动态规划不一定写出来是递归。
回溯法与动态规划
- 共同点：用于求解多阶段决策问题。
- 不同点
- 动态规划只需要求我们评估最优解是多少，最优解对应的具体解是什么并不要求。因此很适合应用于评估一个方案的效果；
- 回溯算法可以搜索得到所有的方案（当然包括最优解），但是本质上它是一种遍历算法，时间复杂度很高。PS：真的碰到一道题，明明要多个解，也在用dp
建议思路：
- 先想递归
- 发现重复计算
- 通过记忆化等方法弄掉重复计算
- 最后看下能不能通过利用计算顺序来做到去掉递归用“刷表”方式直接顺序计算，能搞定最好搞不定拉倒 PS：递归的思维方式更自然一点，除非一眼看出dp怎么做，否则还是别用动态规划。又例如网格问题，上下左右 会搞的dp公式比较复杂。
贪心
贪心算法是指每次根据问题的当前状态，选择一个局部最优策略，并且能够不断迭代，最后产生一个全局最优解。贪心的题目只要求我们想一个合理的局部最优策略，而不需要关注如何证明这个策略能够产生一个全局最优解。
分治
分治法很大程度上也基于递归的思想，两者的区别在于动态规划分解后的子问题是有重复的，而分治法的子问题通常不会重复。 分治法所能解决的问题一般具有以下几个特征。以 “找第K小的数” 的快速选择法来理解下列特征
- 问题的规模缩小到一定程度后可以被很容易解决。
- 问题可以分解为若干个规模较小的相同性质的问题。快速选择法 将某个范围的数移动到一起，这样子问题的规模才能变小，否则你就只能在子区间找第k个数。
- 问题的解等于子问题解的合并。
- 问题分解的各个子问题相互独立，没有重复。 PS：curd ==> 查找 ==> 遍历 = 遍历方法 + 判断函数 ==>
- 优化遍历方法：直接忽略不可能的解（二分、滑动窗口），可以做到o(n)；实在不行，只能分治了。分治也是暴力遍历，但与我们习惯的
for i:=0;i<xxi;i++不同。 - 优化判断函数：虽然全遍历但可以缓存判断函数的计算结果o(n^2)。
小结
分治就是简单的利用递归，没有记忆缓存，而动态规划就有记忆性。直接利用分治递归加上一个记忆功能，许多时候就和动态规划效果一样的，自顶向下，容易思考些。动态规划是从下向上的，如果定义的好，每个子问题只需要计算一次。
计算机并没有“大招”，关键是思维不要乱窜。对一些常见题目，掌握的深度也一定要够，不仅要知道得用dp了，还得知道dp的子状态如何定义。