暴力算法和 DFS 有什么区别？剪枝，回溯又是什么？
在做蓝桥杯的题目时候遇到一个题目，它的描述如下
小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。
有一次，老师出的题目是：
36 * 495 = ?他却给抄成了：
396 * 45 = ?但结果却很戏剧性，他的答案竟然是对的！！
因为
36 * 495 = 396 * 45 = 17820类似这样的巧合情况可能还有很多，比如：
27 * 594 = 297 * 54假设
abcde代表 1~9 不同的 5 个数字（注意是各不相同的数字，且不含 0）能满足形如：
ab * cde = adb * ce这样的算式一共有多少种呢？请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。
满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。
人话来说，就是找出满足ab * cde = adb * ce的所有a b c d e，并且他们数值不会重复，且他们是处于 1-9 这个区间的
解决方案
一共存在两种解决方案，暴力枚举和 DFS。
暴力枚举能比较简单的解决问题，但是它需要走所有的可能才能得出结果，优点在于思想简单容易理解
DFS 解决它的方法可能相对复杂，但是它不不想要知道所有的可能，他会在触碰边界后回退到上一步尝试下一种可能。
跳出这种可能，即为剪枝。
回退到上一步尝试下一种可能，即为回溯。
暴力枚举
我们假设一共有a，b，c，d，e五个循环，其中初始化数据均为 1，包裹顺序为 a 包裹 b 包裹 c 包裹 d 包裹 e，代码如下
for (int a = 1; a < 10; a++) {
for (int b = 1; b < 10; b++) {
for (int c = 1; c < 10; c++) {
for (int d = 1; d < 10; d++) {
for (int e = 1; e < 10; e++) {
// 跳出条件
}
}
}
}
}
能暴力枚举出所有可能，但是这个不是我们的最佳解法——它的范用性非常的差
DFS，深度优先搜索
DFS 一般和全排列在一起，它也能列举出所有的可能并且会尽可能深的访问数据结构，但是它有剪枝和回溯能力以及固定的代码格式，相比之下它有了更强的范用性
它的关键字为：回溯，递归，剪枝
以下为它的伪代码表示
// 这是当前的数据数组，需要看情况调整
ArrayList<Integer> numCombine = new ArrayList<>();
// 需要假设最远步数
int maxStep;
void dfsRun(int step) {
// 边界，maxStep为步数边界
if (step == this.maxStep) {
// 已经到达了边界，需要跳出这一条线路
dfsCheck();
return;
}
// 递归条件
// for语句中填充初始化条件
for (;;) {
// 跳出条件，意味着当前分支已经失败
// 这里就是剪枝操作
if()
continue;
this.numCombine.add(i);
// 走下一步
this.dfsRun(step + 1);
// 回溯，因为这个条件已经判断过了，需要回退一步
this.numCombine.remove(this.numCombine.size() - 1);
}
}
void dfsCheck() {
// 这里写检查条件
// 当检查成功时，可以把它储存起来
}
这就是 DFS 的模板代码了。
用文字的方法来理解它：
1.首先将根节点放入 stack 中。 2.从 stack 中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜寻并回传结果。 否则将它某一个尚未检验过的直接子节点加入 stack 中。
3.重复步骤 2。 4.如果不存在未检测过的直接子节点。
将上一级节点加入 stack 中。 重复步骤 2。
5.重复步骤 4。 6.若 stack 为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
理解起来很困难对吧，没关系来看下面资料继续理解 XD
用到的资源 由 Alexander Drichel - 自己的作品，CC BY-SA 3.0，https://commons.wikimedia.org/w/index.php?curid=3791979