迭代加深搜索就是比朴素 DFS 听起来更帅的 DFS。 —— Weekoder
迭代加深搜索，是一种优化版本的 DFS，也称为 IDDFS。IDDFS 的核心思想非常的简单，那就是：
用 DFS 模拟 BFS！
没错，就是这么简单的一件事。那么，IDDFS 适用于哪些场景呢？事实上，IDDFS 的特征很明显，那就是在搜索树非常大的时候，如果答案在搜索树上的深度很浅，就可以使用 IDDFS。
IDDFS 的好处就是把 DFS 的优点和 BFS 的优点结合了起来。DFS 空间消耗小，不需要存储大量的数据；而 BFS 一层层扩展，对于深度较浅的答案，可以快速找到。但如果我们在上面所说的，一棵非常大非常深的搜索树里搜索的话，两个算法就都不行了：DFS 会超时，因为“不撞南墙不回头”的 ta 很有可能会搜索完一整棵非常非常大的子树再去继续搜索别的子树，而如果答案根本不在搜索的子树里，就会耗费大量时间。BFS 会爆空间，因为随着结点数量的“暴走式”增长，队列很快就会存不下那么多结点了。
那么这个时候，我们就可以用“迭代加深”的思想来解决这类题目：一开始，我们设定一个限制 $\lim$，代表 DFS 最多只能搜索 $\lim$ 层。这个时候我们再去用 DFS 搜索，不就达成了“用 DFS 实现 BFS”的目的了吗？有了 $\lim$ 的限制，DFS 就不再会一口气冲到底了。
接下来的问题是，如果在 $\lim$ 层之内没有搜索到答案咋办？很简单，进一步放宽限制，也就是 lim ++，然后从头再搜一遍。但是，如果每次都要重新搜索一遍，效率不就变低了很多吗？其实不然，比如一棵二叉树，我们知道前 $h$ 层的结点数量为 $2^h-1$，而第 $i$ 层的结点数量为 $2^{i-1}$。也就是说，一棵 $h$ 层的完美二叉树的最后一层的结点数量（$2^{h-1}$）比前面所有结点的数量（$2^{h-1}-1$）还要多 $1$！更别说是一棵巨大的多叉搜索树了，因为随着层数的增加，结点的数量是指数级增长（增长得非常非常快）的。这时候就算从头开始搜也只是相当于多了一点常数而已。
但如果我偏偏不想搜重复的状态呢？能不能记忆化，从上一次搜索结束的地方开始继续搜索？这是一个很好的想法，但与我们之前的困扰完全矛盾了：如果我能记忆化，为什么不 BFS 呢，因为我们都花了那么多空间去记忆化了。记忆化本质上就是在用空间换取时间，而这里我们的问题就是空间不够，所以根本无法记忆化，而即使这么做也只是将时间减半了而已，就像 $2$ 百万和 $1$ 百万的区别一样，都一样很大。
好了，现在来看看 IDDFS 的代码怎么实现吧，例题在这儿 → Addition Chains - POJ 2248 - Virtual Judge (vjudge.net) ← 对了，记住一定要选我（Leon0328）的翻译，我翻译得最好O(∩_∩)O。加油，思考一下！
怎么样，有想法吗？这是个搜索问题，这很容易分析出来，因为我们能做的只有枚举接下来的数字。想到搜索后，首先我们得判断答案的深度是否较浅，才能 IDDFS，这是使用 IDDFS 的前提。样例就是一个很好的解释：当 $n=77$ 时，加法链的长度也只有 $9$，而 $n$ 最大只有 $100$，对于 $100$ 的加法链能有 $20$ 个数就算了不起了，所以答案的深度是很浅的。
于是我们可以一层一层地搜，以加法链的长度作为搜索树的深度。如果到第 $\text{dep}$ 层第一次搜到答案了，那么加法链的长度就是 $\text{dep}$。
对于 IDDFS，我们有一个比较通用的格式，那就是使用 bool 类型的 DFS 返回值，代表当前深度有没有搜索到答案。参数要带一个 $\text{cur}$，代表当前搜索到的深度，还可以带一些其他的参数记录答案。在函数内，如果递归下去的子函数返回真，那么 DFS 函数立刻返回真，因为已经在子树里搜索到答案了。代码示例：
bool dfs(int cur, ...) {
if (cur == lim) return ...; // 达到搜索限制。前面的区域，以后再来探索吧！
...
for (...) { // DFS 内的常规枚举操作~
...
if (dfs(cur + 1, ...) == true) {
return true; // 如果子树已经搜到答案了，那就代表我也搜到答案了，因为子树的东西就是我的东西！
}
...
}
return false; // 每个子树内都没搜到答案，我这里看来是搜不到答案了（举白旗）
}
对于这道题的话，我们还需要记录一个 $ans$ 数组用于存储当前已经选择的加法链。那么根据题目中的条件 $a_k=a_i+a_j$，我们就可以从已有的加法链中任选两个元素加起来并构造一个 $a_k$，继续向下 DFS。注意，这里选的两个数可以是同一个数，也就是 $i$ 可以等于 $j$。这样，我们就得到了加法链中的下一个元素。
当 $cur=\lim$，也就是搜索到达限制的时候，我们的函数就可以直接返回一个布尔值（$\text{}$true or false），也就是当前是否已经找到了答案。很明显，在这道题目中，如果我们能成功让最后一个元素变为 $n$，就找到了一个答案。
还有几点要注意的是：