这个蓝桥杯高频考点，省赛前说啥都得过一遍！

可以很好地帮助我们在赛场上有效拿分！

今天，我们来看蓝桥杯C/C++ B组冠军学长 肖志林 给我们分享——《临考突击蓝桥杯高频考点:搜索题型》。

搜索其实就是“高级的”枚举，很多题目其实都可以用搜索来完成。常见的搜索框架算法有：DFS（深度优先搜索）、BFS（广度优先搜索），进阶搜索：搜索剪枝，A*，折半等等。

大部分情况下，我们采用DFS或者BFS的框架，去遍历题目的每个状态，以此来获得最优解。一般来讲，会分为以下5步👇：

这里，我们用蓝桥杯的往届真题📑来举例子：

这是一道典型的搜索题目，由于数据范围较小，可以采用暴力枚举的方式进行搜索，具体来说，可以采用深度优先搜索(DFS)的方式：

首先，我们需要明确题目要求✨：

题目要求将两种糖果分别分给7个小朋友，每个小朋友得到的糖果总数最少为2个最多为5个，问有多少种不同的分法，糖果必须全部完全分完，只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。

接下来，我们需要分析约束/限制条件，给出解题步骤👇。

由于这是一道搜索题目，我们可以采用📍深度优先搜索(DFS)的方式进行求解，具体来说：

• 在递归的过程中，我们需要对每个小朋友分到的糖果数量进行限制，这个限制条件可以放在函数的参数中进行传递，也可以放在函数内部进行检查

• 具体来说，每次递归到下一个小朋友时，我们需要枚举他分到第一种糖果的数量，从而推出他分到第二种糖果的数量。

在枚举的过程中，需要注意一些细节，比如：

递归的出口是：当目前正在分配糖果的小朋友的编号为7时，需要判断第七个小朋友分到的糖果数量是否满足限制条件？如果满足，则累加答案。

最后，需要注意一些细节问题，比如：

✅需要将答案初始化为0

✅需要在递归出口处判断第七个小朋友分到的糖果数量是否满足限制条件

✅适当把不满足条件的方案进行减枝

在每一层的搜索中，每个小朋友最多有9种可能的糖果分配情况，而最多只需要枚举5种糖果分配情况，因此，每层最多只需要进行10次搜索。

由于总共需要进行7层搜索，所以，总的搜索次数不会超过10^7次。

这也进一步说明了，这道题目的时间复杂度是可以接受的，可以用暴力枚举的方式进行求解。

搜索是一类很重要和常见的算法，掌握好搜索算法，基本能解决大部分毫无头绪的问题。但是，搜索算法往往时间或者空间上限制较大，这时候就需要考虑其他算法。不过，从另一方面来说，即使是考察其他算法的题目，搜索算法仍能帮你得到部分分数。对于一部分题目（规律类的数学题），使用搜索也可能帮助你发现一些不易察觉的规律。