DFS（基础，回溯，剪枝，记忆化）搜索

DFS基础

DFS(深度优先搜索)

基于递归求解问题，而针对搜索的过程

对于问题的介入状态叫初始状态，要求的状态叫目标状态

这里的搜索就是对实时产生的状态进行分析检测，直到得到一个目标状态或符合要求的最佳状态为止。对于实时产生新的状态的过程叫扩展
搜索的要点:
1.选定初始状态，在某些问题中可能是从多个合法状态分别入手搜索:
2. 遍历自初始状态或当前状态所产生的合法状态，产生新的状态并进入递归;
3，检查新状态是否为目标状态，是则返回，否则继续遍历，重复2-3步骤

常用模板

public static void dfs(){if(当前状态==目标状态)return;for(寻找新状态){if(状态合法){dfs(新状态);}}}

例题实战

---

 DFS回溯

概念

回溯算法的基本思想是:从一条路往前走，能进则进，不能进则退回来，换一条路再试，从而搜索到抵达特定终点的一条或者多条特定路径。
回溯在于“状态”。在回溯算法向前的每一步，你都会去设置某个状态，而当向前走走不通的时候回
退，此时需要把之前设置的状态撤销掉。

模板

public static void dfs(){if(当前状态==目标状态){return;}for(查找新状态){if(状态合法){dfs(新状态);}}
}

例题实战

1.输入一个数组n,输出1到n的全排列

2.人类的开心程度有高低之分，数字也一样

给定一个正整数 n，在n 的数位之间插入k 个加号，使其变成一个表达式，计算得出的结果就是 n

的一个k级开心程度

例n=1234，k=1时，我们可以往 2和3之间插入一个+号，使其变为 12 +34

计算出结果为 46，那么46就是1234 的一个k级开心程度

给定 n,k请你计算出 n 的k级开心程度的最大值与最小值之差

输入格式

一行输入两个正整数 n,，含义见题面

输出格式

一行一个整数，表示 n的k级开心程度的最大值与最小值之差
样例输入

12341

输出样例

169

（答案后期更新）

---

DFS剪枝

概念

在搜索算法中优化就称为剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就

剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确

哪些枝条应当舍弃，哪些枝条应当保留的方法。

概况：在进行搜索算法的过程中，将已知无意义的情况排除的行为叫做剪枝

复杂度过大的必须进行剪枝才能通过测试

 例题实战

假设一个三角形三条边为 a、b、c，定义该三角形的值 = a xbxc
现在有t个询问，每个询问给定一个区间[l,r]，问有多少个三条边都不相等的三角形的值v在该区间范围内
输入格式
第一行包合一个正整数 t，表示有t个询问
接下来t行，每行有两个空格隔开的正整数l，r表示询问区间[l,r]
输出格式
输出共l行，第i行对应第i个查询的三角形个数

(答案下次见)

记忆化搜索

记忆化概念

什么是记忆化搜索呢?

记忆化搜索是在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少复搜索量

记忆化搜索的核心实现

1.首先，要通过一个数组记录已经存储下的搜索结果

2.状态表示，由于是要用数组实现，所以状态最好可以用数字表示，

3.在每一状态搜索的开始，高效的使用数组查看这个状态是否出现过，如果已经做过，直接调用答案，如果没有，则按正常方法搜索

例题实战

小蓝有一天误入了一个混境之地
好消息是:他误打误撞拿到了一张地图，并从中获取到以下信息:
1.混境之地是一个n·m 大小的矩阵，其中第i行第j列的的点 h 表示第i行第j列的高度。
2.他现在所在位置的坐标为(A,B)，而这个混境之地出口的坐标为(C,D),当站在出
口时即表示可以逃离混境之地。
3.小蓝有一个喷气背包，使用时，可以原地升高人 k个单位高度
坏消息是:
1.由于小蓝的体力透支，所以只可以往低于当前高度的方向走
2.喷漆背包燃料不足，只可以最后使用一次
小蓝可以往上下左右四个方向行走，不消耗能量
小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，输入 Yes ，反之输出 No。
输入格式
第1行输入三个正整数 n,m 和k， n,m 表示混境之地的大小，k 表示使用一次喷气背
包可以升高的高度。
第2行输入四个正整数A,B,C,D，表示小当前所在位置的坐标，以及混境之地出口。