分层dfs，一种介于dfs与bfs之间的算法

在算法设计的深邃丛林中深度优先搜索与广度优先搜索如同两条风格迥异的小径。前者沿着一条道路走到黑不撞南墙不回头却往往在最优解的门口徘徊——它难以回答最少需要几步这样的问题因为一旦深入某个分支它不关心其他路径是否更短。后者则像水波般层层扩散保证第一次抵达目标时经过的步数最少却常常面临队列爆炸的困境当解空间呈指数级膨胀时那庞大的内存开销足以让最强劲的计算机望而却步。正是在这样的张力之间一种兼具二者优长的策略悄然生长分层搜索或称迭代加深搜索。它本质上是一种带有深度限制的深度优先搜索却又保留了广度优先的层序特性。不再是一次性地将所有可能塞入队列等待处理也不再是盲目地沿着单一路径探寻至不可知的深处而是设定一个界限只允许搜索在限定的层数内展开。若在此界限内未能觅得目标便将界限放宽一层在新的深度范围内重新探索。如此往复直至答案浮现。这种策略的精妙之处在于它对问题结构的深刻洞察。许多组合优化问题天然携带着代价的维度——使用的元素个数、经历的步数、消耗的权重——这些代价通常是正整数且我们往往渴求其最小值。传统的动态规划试图在一次遍历中计算出所有子问题的最优解犹如绘制一幅完整的地图无论目的地在何方都要将沿途的每一寸土地勘测完毕。而分层搜索则采取了一种更为务实的姿态它假设答案可能隐藏在较浅的层次先用最少的资源试探第一层若不得再增加一分投入试探第二层层层递进一旦触及目标即刻收兵绝不在无谓的深处虚耗光阴。以 LeetCode 279 题「完全平方数」为例这种思想展现得淋漓尽致。题目要求我们给定正整数 n寻找若干完全平方数使其和为 n并最小化所使用的数字个数。若采用常规的广度优先搜索我们需要维护一个队列记录每一个数值及其对应的步数随着步数增加队列中的状态可能膨胀至难以控制。但若转换视角不再按数值展开搜索而是按已使用的数字个数这一维度来组织探索局面便豁然开朗。我们构建一个二维的布尔空间其横轴是待凑成的数值纵轴是已使用的完全平方数个数。从原点出发第零层仅有数字零可达代表尚未使用任何数字。第一层则标记所有单个完全平方数所能触及的数值——1、4、9、16依此类推。若目标 n 恰好位于这一层我们便已得解。否则进入第二层将第一层中所有可达的数值分别加上各个完全平方数得到新的可达集合这对应着使用两个完全平方数的所有可能。如此递推每一层都是前一层的自然延伸通过简单的加法操作便能生成。根据数学上的四平方和定理任何正整数皆可在四层之内被表示这意味着我们的搜索深度天然受限既无需担忧无限循环也不必为深层递归的栈溢出而焦虑。具体的实现优雅而简洁。我们预先生成所有候选的完全平方数然后初始化一个二维数组graph其中graph[k][j]记录能否用恰好 k 个数字凑出 j。代码的核心循环便是逐层填充这个数组对于第 k-1 层中每一个为真的位置 j我们遍历所有平方数 s将graph[k][js]标记为真。每层填充完毕后立即检查目标 n 是否已在当前层现身一旦命中即刻返回层数 k。这种写法避免了传统动态规划中必须计算从 1 到 n 所有子问题的冗余也规避了 BFS 中队列维护的开销以数组的随机访问实现了近乎理想的时间效率。279. 完全平方数 - 力扣LeetCode题目描述给你一个整数n返回和为n的完全平方数的最少数量。完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。#includestdbool.h#includestring.h#includemath.hintnumSquares(intn){// 预处理所有可用的完全平方数作为搜索的基础元素intmax_n(int)sqrt(n);intsquares[101];intsq_cnt0;for(inti1;imax_n;i){squares[sq_cnt]i*i;}// 构建分层搜索空间graph[k][j] 表示恰好用 k 个平方数能否组成 j// 根据四平方和定理k 最大只需到 4bool graph[5][n1];memset(graph,0,sizeof(graph));// 第零层零个数字只能凑出零graph[0][0]true;// 第一层初始化所有单个平方数可达的位置for(inti0;isq_cnt;i){if(squares[i]n)graph[1][squares[i]]true;}if(graph[1][n])return1;// 提前终止n 本身就是完全平方数// 迭代加深逐层扩展搜索范围for(intk2;k4;k){// 基于第 k-1 层的所有可达状态推导第 k 层for(intj0;jn;j){if(!graph[k-1][j])continue;// 剪枝只处理前一层可达的状态// 尝试添加每一个平方数生成新的可达数值for(ints0;ssq_cntjsquares[s]n;s){graph[k][jsquares[s]]true;}}// 每层搜索结束后立即检验目标if(graph[k][n])returnk;}return4;// 数学定理保证答案不超过 4}这种分层搜索的策略并不局限于数字拆分问题。在任何需要最小化操作步数、且每步操作具有可加性的场景中它都能大显身手。比如寻找最短编辑距离、计算最小换乘次数或是博弈论中寻找最少步数的必胜策略。它教会我们有时候不必一次性看清整张地图而是可以带着探照灯一圈一圈地扩大搜索半径直到光明触及目标。这种渐进式的探索既保留了深度优先的简洁与低内存占用又拥有广度优先的最优性保证堪称算法设计中的一种平衡艺术。