【每日一题】深度优先搜索（DFS）

写在前面DFS深度优先搜索是算法竞赛中最基础也最核心的搜索算法之一。它不仅是图论遍历、连通性判断的基础更是全排列、组合枚举、状态空间搜索等高级技巧的基石。本文基于蓝桥杯官方课程与真题从DFS基础到竞赛实战带你彻底掌握深度优先搜索一、DFS基础从暴力枚举到深度优先1.1 什么是DFS搜索算法的本质穷举问题解空间的部分/所有情况从而求出问题的解。深度优先搜索的核心思想本质上是暴力枚举深度优先尽可能一条路走到底走不通再回退回溯1.2 DFS vs 普通循环对比项普通循环DFS适用场景固定层数的枚举动态层数的枚举代码结构for嵌套递归函数灵活性层数固定后难以修改通过参数控制层数回溯机制无自动回溯1.3 DFS的图论直觉如何寻找从节点1走到节点8的路径从1出发只要发现有没走的点就走走不了就回退按照上述准则一定能从1走到8示例路径1-3-7-A-7-9-3-5-6-8红色部分表示回退核心洞察将问题建模成图的形式深度优先搜索可以暴力求解很多问题二、DFS和n重循环从三重循环到n重循环2.1 问题引入问题给定一个数字x将其拆分成3个正整数后一个要求大于等于前一个给出所有方案。最简思想三重循环暴力求解但如果要拆分成4个正整数呢n个正整数呢就需要实现n重循环n重循环 特定的树状结构 DFS搜索2.2 树状结构理解以x6拆分成3个正整数为例n重循环n层的树DFS从上往下找一条合法的路径路径值不递减、长度为n、和为x树的第一层第0重循环选择第一个数1~6树的第二层第1重循环选择第二个数第一个数树的第三层第2重循环选择第三个数第二个数2.3 基础DFS代码未剪枝x,nmap(int,input().split())# 记录每层选择的数字a[0]*n# 计算次数cntcnt0defdfs(depth):globalcnt cntcnt1# 第0重 ~ 第n-1重都已经选好数字此时只需要判断答案ifdepthn:# 条件一数字需要递增非递减foriinrange(1,n):ifa[i]a[i-1]:continueelse:return# 条件二数字和为xifsum(a)!x:return# 此时是合法答案print(a)return# 第depth层进行选择数字[1, x]进行枚举foriinrange(1,x1):# 选择第depth层的数字a[depth]i# 递归进入下一层dfs(depth1)dfs(0)print(累计计算次数{}.format(cnt))2.4 剪枝优化把条件放在枚举时判断核心思想在搜索过程中提前判断不合法的情况减少搜索量。defdfs(depth,last_val):globalcnt cntcnt1# 第0重 ~ 第n-1重都已经选好数字ifdepthn:# 条件二数字和为xifsum(a)!x:return# 此时是合法答案print(a)return# 第depth层进行选择数字# 剪枝只枚举[last_val, x]保证非递减foriinrange(last_val,x1):a[depth]i# 递归进入下一层下一层的最小值就是idfs(depth1,i)dfs(0,1)优化效果通过last_val参数直接在枚举时保证非递减避免了大量无效搜索2.5 DFS模板defdfs(depth):ifdepthN:# N重循环最内层执行的代码return# 每重循环进行的枚举选择forchoiceinchoices:# 做出选择# 递归进入下一层dfs(depth1)# 撤销选择回溯三、每日一题实战演练题目1分糖果 7重循环 多状态DFS题目链接蓝桥杯4124题目描述两种糖果分别有9个和16个要全部分给7个小朋友每个小朋友得到的糖果总数最少为2个最多为5个问有多少种不同的分法。糖果必须全部分完。核心思路7重循环每重循环表示1个小朋友每个小朋友枚举所有糖果情况第一种糖果i个第二种糖果j个需要满足2 ij 5且剩余糖果足够ans0defdfs(depth,n,m):globalans# 7个小朋友都分配完毕ifdepth7:# 糖果必须全部分完ifn0andm0:ans1return# 枚举第一种糖果数量0~5foriinrange(0,6):# 枚举第二种糖果数量0~5forjinrange(0,6):# 条件总数在2~5之间且不超过剩余数量if2ij5andinandjm:dfs(depth1,n-i,m-j)dfs(0,9,16)print(ans)复杂度时间取决于剪枝效果最坏O(6^14)实际远小于此关键细节depth表示第几个小朋友从0开始n和m是剩余糖果数量递归时减去分配的数量枚举范围range(0, 6)即0~5因为每个小朋友最多5个最终判断n 0 and m 0保证全部分完题目2买瓜 N重循环 三状态DFS题目链接蓝桥杯3505题目描述瓜摊上有n个瓜每个瓜重量为A_i。小蓝可以把任何瓜劈成完全等重的两份每个瓜只能劈一刀。希望买到的瓜的重量和恰好为m。问至少要劈多少个瓜如果无法得到输出-1。核心思路N重循环每重循环三种情况买1个、买半个劈一刀、不买用DFS枚举所有情况记录最小劈瓜次数defdfs(depth,s,cnt):globalans# 剪枝1当前累计重量已经超过m不需要继续下去ifsm:return# 剪枝2当前累计重量等于m直接更新答案ifsm:ansmin(ans,cnt)return# 剪枝3第depth层时停止继续递归所有瓜都考虑完了ifdepthn:return# 情况1买整个瓜dfs(depth1,sw[depth],cnt)# 情况2买半个瓜劈一刀dfs(depth1,sw[depth]//2,cnt1)# 情况3不买这个瓜dfs(depth1,s,cnt)# 主程序n,mmap(int,input().split())m*2# 避免浮点数全部乘以2wlist(map(int,input().split()))w[x*2forxinw]# 重量也乘以2ansn1# 初始化一个不可能的最大值dfs(0,0,0)ifansn1:ans-1print(ans)复杂度时间O(3^n)通过剪枝可大幅降低关键细节避免浮点数将m和w都乘以2用整数运算ans n 1作为初始值如果最终没变说明无解三种情况按顺序枚举买整个、买半个、不买剪枝策略超界直接返回、找到解更新最优值、深度到达n停止四、DFS专题应用场景总结应用场景DFS技巧时间复杂度代表题目n重循环替代递归替代嵌套循环O(k^n)数字拆分剪枝优化在枚举时加入约束条件大幅降低数字拆分非递减版多状态DFS多个参数传递状态O(状态数)分糖果多选择DFS每层多种选择分支O(分支数^深度)买瓜回溯标记选择-递归-撤销O(状态数)全排列、N皇后记忆化搜索DFS 缓存结果O(状态数)斐波那契、路径计数五、结语DFS的魅力在于将复杂的n重循环转化为清晰的递归结构配合剪枝让暴力枚举也能高效求解。当你熟练运用这些技巧后很多看似复杂的组合、排列、状态搜索问题都会迎刃而解。学习建议理解DFS与n重循环的等价关系培养循环-递归的转化思维重点掌握剪枝技巧它是DFS从超时到通过的关键学会设计DFS的参数深度、状态、约束条件关注多状态DFS它是处理复杂问题的利器多练习多选择分支类问题理解状态空间搜索的本质如果本文对你有帮助欢迎点赞 收藏 关注你的支持是我持续更新的动力