备战蓝桥杯国赛【Day 20】

📌 写在前面：DFS（深度优先搜索）是算法竞赛中最基础也最核心的算法之一。它不仅能替代n重循环实现枚举，更是回溯、剪枝、状态压缩等高级技巧的基础。本文基于蓝桥杯官方课程与真题，从DFS替代n重循环到剪枝优化，带你彻底掌握DFS！

📚 今日题单

一、DFS基础：从n重循环到递归树

1.1 核心思想

问题：给定数字 x，拆分成 n 个正整数，后一个 >= 前一个。

三重循环写法（n=3时）：

foriinrange(1,x+1):forjinrange(i,x+1):forkinrange(j,x+1):ifi+j+k==x:print(i,j,k)

DFS写法（通用，适用于任意n）：

path=[0]*n# path[i]表示第i个数字defdfs(depth,last_value):""" depth: 当前处于第depth层（已确定depth个数） last_value: 上一层的取值（保证后一个>=前一个） """# 递归出口：已确定n个数ifdepth==n:ifsum(path)==x:print(path)return# 枚举当前位置的取值foriinrange(last_value,x+1):path[depth]=i# 做选择dfs(depth+1,i)# 进入下一层# path[depth] = 0 # 回溯（可选，因为会被覆盖）dfs(0,1)

1.2 为什么DFS能替代n重循环？

n重循环 = 特定的树状结构 = DFS搜索 以x=6, n=3为例： 0(根) / | | | | \ 1 2 3 4 5 6 <- 第一重循环/第一层DFS /| 1 2 3 4 5 6 <- 第二重循环/第二层DFS /| 1 2 3 4 5 6 <- 第三重循环/第三层DFS

DFS的本质：用递归模拟多叉树的深度优先遍历，每一层递归对应一重循环。

1.3 DFS三大要素

二、分糖果2023 DFS枚举+剪枝

2.1 题目描述

两种糖果分别有9个和16个，全部分给7个小朋友。每个小朋友得到的糖果总数最少为2个，最多为5个。问有多少种不同的分法？

注意：只要有一个小朋友在两种方案中分到的糖果不完全相同，就算不同的方案。

2.2 关键思路

DFS设计：

• depth：第几个小朋友（0~6）
• n：第一种糖果剩余数量
• m：第二种糖果剩余数量
• 枚举当前小朋友分到的两种糖果数量(i, j)

剪枝优化：

1. 可行性剪枝：i + j必须在[2, 5]范围内
2. 剩余数量剪枝：i <= n且j <= m
3. 提前终止：如果剩余糖果不够分或太多，提前返回

2.3 版本1：暴力DFS（无剪枝，慢）

ans=0path=[[0,0]for_inrange(7)]# path[i][0]表示第i个小朋友的第一种糖果数defdfs1(depth):"""暴力版本：只判断最终状态是否合法"""ifdepth==7:sum1,sum2=0,0foriinrange(7):sum1+=path[i][0]sum2+=path[i][1]ifsum1==9andsum2==16:globalans ans+=1return# 枚举当前小朋友的糖果foriinrange(6):# 第一种糖果 0~5forjinrange(6):# 第二种糖果 0~5if2<=i+j<=5:path[depth][0]=i path[depth][1]=j dfs1(depth+1)dfs1(0)print(ans)# 5067671

问题：枚举了大量不可能的状态，效率低。

2.4 版本2：剪枝DFS（推荐）

ans=0defdfs(depth,n,m):""" depth: 第depth个小朋友 n: 第一类糖果剩余数量 m: 第二类糖果剩余数量 """# 递归出口：分完所有小朋友ifdepth==7:ifn==0andm==0:# 糖果恰好分完globalans ans+=1return# 剪枝1：剩余糖果不够分（每个小朋友至少2个）ifn+m<2*(7-depth):return# 剪枝2：剩余糖果太多（每个小朋友最多5个）ifn+m>5*(7-depth):return# 枚举当前小朋友的糖果foriinrange(min(n,5)+1):# 第一种糖果 0~min(n,5)forjinrange(min(m,5)+1):# 第二种糖果 0~min(m,5)# 剪枝3：总数必须在[2,5]范围内if2<=i+j<=5:dfs(depth+1,n-i,m-j)dfs(0,9,16)print(ans)# 5067671

复杂度：大量剪枝后，实际运行效率提升数十倍。

2.5 关键细节

三、买瓜 DFS+剪枝

3.1 题目描述

n 个瓜，重量为 A_i。小蓝可以把任何瓜劈成完全等重的两份（每个瓜只能劈一刀）。希望买到的瓜的重量和恰好为 m。求至少要劈多少个瓜？如果无法做到，输出 -1。

数据范围：n <= 30，A_i <= 10^9

3.2 关键思路

状态设计：

• depth：第几个瓜
• weight：当前买到瓜的总重量
• cnt：当前劈的瓜的数量

三种选择：

1. 不买：dfs(depth+1, weight, cnt)
2. 买整个：dfs(depth+1, weight + A[depth], cnt)
3. 买一半（劈一刀）：dfs(depth+1, weight + A[depth]//2, cnt+1)

精度处理技巧：

• 所有重量乘以2，避免浮点数
• 目标 m 变成 m * 2
• 买一半变成A[i]（原重量的一半 * 2 = 原重量）

3.3 题解

defdfs(depth,weight,cnt):""" depth: 第depth个瓜 weight: 当前买到瓜的总重量（已乘2） cnt: 当前劈的瓜的数量 """# 最优性剪枝：当前已经比已知答案差ifcnt>=ans:return# 可行性剪枝：重量已经超过目标ifweight>m:return# 找到合法解ifweight==m:globalans ans=min(ans,cnt)return# 递归出口：所有瓜都考虑完了ifdepth==n:return# 选择1：不买这个瓜dfs(depth+1,weight,cnt)# 选择2：买整个瓜dfs(depth+1,weight+a[depth],cnt)# 选择3：买半个瓜（劈一刀）dfs(depth+1,weight+a[depth]//2,cnt+1)n,m=map(int,input().split())a=list(map(int,input().split()))# 精度处理：所有重量乘以2m*=2a=[i*2foriina]ans=n+1# 初始化为最大值dfs(0,0,0)ifans==n+1:ans=-1print(ans)

3.4 推演验证

输入: n=3, m=10, A=[1, 3, 13] 精度处理后: m=20, A=[2, 6, 26] 目标: 重量和 = 20 DFS过程: depth=0, weight=0, cnt=0 - 不买A[0]=2: dfs(1, 0, 0) - 不买A[1]=6: dfs(2, 0, 0) - 不买A[2]=26: dfs(3, 0, 0) -> depth==3, weight!=20, 返回 - 买A[2]=26: dfs(3, 26, 0) -> weight>20, 剪枝 - 买半A[2]=13: dfs(3, 13, 1) -> depth==3, weight!=20, 返回 - 买A[1]=6: dfs(2, 6, 0) - 不买A[2]: dfs(3, 6, 0) -> 不合法 - 买A[2]=26: dfs(3, 32, 0) -> 剪枝 - 买半A[2]=13: dfs(3, 19, 1) -> depth==3, weight!=20, 返回 - 买半A[1]=3: dfs(2, 9, 1) - 不买A[2]: dfs(3, 9, 1) -> 不合法 - 买A[2]=26: dfs(3, 35, 1) -> 剪枝 - 买半A[2]=13: dfs(3, 22, 2) -> weight>20, 剪枝 - 买A[0]=2: dfs(1, 2, 0) ...类似展开 - 买半A[0]=1: dfs(1, 1, 1) ...类似展开 最终找到: 买半A[0]=1 + 买A[1]=6 + 买半A[2]=13 = 20 cnt = 2（劈了A[0]和A[2]） 输出: 2

3.5 关键细节

3.6 进一步优化

对于 n=20 的数据，DFS可能超时。可以考虑：

1. 折半搜索：将20个瓜分成两组10个，分别枚举后合并
2. 排序+优先搜索大瓜：先处理大重量瓜，更快接近目标

💡 今日核心收获

1. DFS替代n重循环：DFS的本质是递归树，每层递归对应一重循环，通用性更强。
2. 状态设计：dfs(depth, ...)的参数设计直接影响剪枝效果和代码简洁度。
3. 剪枝三原则：
   • 可行性剪枝：当前状态已经不合法，直接返回
   • 最优性剪枝：当前状态已经不如已知最优解，直接返回
   • 边界剪枝：利用题目约束提前判断不可能的情况
4. 精度处理：涉及"一半"等分数时，全部乘2转整数，避免浮点数误差。
5. DFS vs 循环：n不确定时用DFS，n确定且小时用循环，DFS更灵活但常数更大。

📌 DFS常见应用场景

📌 DFS模板总结

基础DFS模板（枚举型）

defdfs(depth,state):""" depth: 当前深度/层数 state: 当前状态（根据题目设计） """# 1. 剪枝（可选）ifnotvalid(state):returnifnotbetter_than_best(state):return# 2. 递归出口ifdepth==n:update_answer(state)return# 3. 枚举选择forchoiceinchoices:# 做选择make_choice(choice)# 进入下一层dfs(depth+1,new_state)# 回溯（可选）undo_choice(choice)

图DFS模板

defdfs(u):visited[u]=Trueforvingraph[u]:ifnotvisited[v]:dfs(v)

📌 剪枝技巧总结

如果本文对你有帮助，欢迎点赞 + 收藏 + 关注，你的支持是我持续更新的动力！