1119蓝桥杯：回溯法、剪枝、记忆化搜索_搜索与剪枝 原理实现

一、回溯法

回溯法一般使用DFS_(深度优先搜索) 实现，DFS是一种遍历或搜索图、树或图像等数据结构的算法，当然这个图、树未必要存储下来(隐式处理就是回溯法)常见的是通过某种关系构造出的搜索树，搜索树一般是排列型搜索树 (总节点个数一般为n!级别) 和子集型搜索树(总节点个数一般为2^n级别)。

排列型就是每次枚举选哪个，子集型就是对于每一个元素选或不选(结果与顺序无关)

DFS从起始节点开始，沿着一条路径尽可能探人地搜索（一条路走到黑），直到无法继续为止，然后回溯到前一个节点,继续探索其他路径，直到遍历完整个图或树。

DFS使用栈或递归来管理节点的遍历顺序，一般使用递归。

很多时候DFS和回溯法不必过度区分。

模板：

二、剪枝

其实就是将搜索过程当中一些不必要的部分直接剔除掉，因为搜索过程构成了一棵树，剔除不必要的部分，就像是在树上将树枝剪掉，故名剪枝剪枝是回溯法的一种重要优化手段，方法往往先写一个暴力搜索，然后找到某些特殊的数学关系，或者逻辑关系，通过它们的约束让搜索树尽可能浅而小，从而达到降低时间复杂度的目的，一般来说，剪枝的复杂度难以计算。

三、记忆化

就是将搜索过程中会重复计算且结果相同的部分保存下来，作为一个状态，下次访问到这个状态时直接将这个子搜索的结果返回，而不需要再重新算一遍。

通常会使用数组或map来进行记忆化，下标一般和dfs的参数表对应。

注意使用记忆化需要保证重复计算的结果是相同的，否则可能产生数据失真。