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的子状态如何定义。
