深度优先搜索DFS这个名字听起来挺吓人其实说白了就是“一条道走到黑撞了南墙再回头”。但真正在做题或写项目时你会发现裸的DFS经常超时数据量稍微大一点就跑不动。这时候剪枝就成了救命的家伙。我从开始学算法到现在经历过“DFS只会暴力枚举”到“学会用剪枝把指数级搜索缩到可接受范围”的过程踩过不少坑也总结出一些自己的理解。这篇就完全用大白话把深度优先搜索剪枝这件事讲清楚从概念到实操再到常见的坑希望能帮你少走弯路。剪枝到底解决什么问题一句话搜索树太大跑不完。深度优先搜索本质是在一棵隐式的树上做遍历每到一步就尝试所有可能然后递归往下走。问题是很多分支从一开始就没希望或者已经不可能比已知答案更好却还是要傻乎乎地走下去白白浪费计算量。剪枝就是在递归深入之前先判断这个分支值不值得走不值得就直接“剪”掉return 回去。它不改变搜索的逻辑只是让搜索少做无用功。这篇文章适合谁如果你是算法新手刚接触DFS和回溯这篇能帮你建立直觉如果你已经写过一些DFS但总是超时这篇能帮你梳理剪枝的思路和技巧。我会从直觉讲起再用实际例子一步步加剪枝最后分享一些排查问题的经验。1. 先从直觉上把深度优先搜索讲透1.1 递归就是一条道走到黑第一次学DFS很多人被“递归”“回溯”“栈”这些词绕晕。我自己的理解特别简单DFS就是“一条道走到黑走不动了再退回来走另一条”。想象你在一个迷宫里面没有地图也没人告诉你哪条路通。你要走出迷宫最笨的办法是什么顺着一条路一直走遇到岔路口就选一个方向继续走。如果走到死胡同就退回到上一个岔路口换一个方向再走。这个过程就是深度优先搜索优先往深处走走不通再回头。用代码写的话核心就是一个递归函数def dfs(step, state): if step target: # 到达终点 handle(state) return for choice in choices: if valid(choice): # 这一步能不能走 state.append(choice) dfs(step 1, state) state.pop() # 回溯这里有个容易混淆的点state.append和state.pop成对出现这就是“回溯”的本意。当你尝试了一个方向递归返回之后要把状态恢复原样不然会影响下一个方向的尝试。这个细节我一开始老漏尤其是用字符串拼接或者传列表的时候不恢复状态就会导致结果错乱。有些人会问DFS和递归是一回事吗不是但DFS通常用递归实现因为递归天然有“调用栈”帮我们记住每一层走到了哪。你也可以用栈自己模拟但那样代码会复杂不少。我自己在刷题时除非是怕递归栈溢出否则都用递归写直观且容易调试。1.2 为什么裸DFS常常超时DFS的时间复杂度通常是指数级的。你想想每一步平均有 m 个选择要走 n 步那整棵搜索树的节点数大约是 m^n 量级。哪怕每个节点只处理 1 毫秒m2、n30 时就是 10 亿量级显然跑不动。举一个特别典型的场景给你一个数组要你从里面选若干个数使它们的和等于某个目标值。如果直接用DFS枚举所有子集那 20 个元素的数组就有 2^20 100 多万种情况勉强能跑30 个元素就是 10 亿级别直接卡死。这种问题如果不去想办法减少搜索分支复杂度是不可能降下来的。有人会说那能不能多线程并行或者换成BFSBFS同样会遍历整棵搜索树只是层序外扩复杂度并没有掉量级。真正想做的是“让树变小”剪枝就是干这个的。另一个容易忽略的点是DFS递归本身有开销。每递归一层都要压栈、传参、恢复现场如果搜索空间本来就大再加上这个开销就会更慢。所以剪枝不只是优化“搜索次数”也是在优化“实际运行的常数”。2. 剪枝到底是什么砍掉注定没戏的分支2.1 用生活类比理解剪枝我说一个特别形象的例子你在衣柜里挑明天穿的衣服。你有规则上衣和裤子要搭配且不能是红色配绿色假设你觉得丑。你从一堆衣服里一件件试试到一套绿裤子的时候发现它和已经选好的红上衣冲突你会怎么做正常人不是继续把剩下的白袜子黑袜子都试一遍而是直接把这套组合否掉马上换下一条裤子。这个“直接否掉”的动作放在搜索里就是剪枝。搜索树上的每个“节点”代表一个部分状态比如“我已经选了红上衣”“我已经选了红上衣和绿裤子”。到了第二个节点你已经知道它违反规则了那就不需要再往下展开“配白袜子”“配黑袜子”这些无意义的子分支。所以我对剪枝的定义就一句话在递归深入之前用一个快速判断把不可能通往正确答案的分支直接砍掉。它不会漏掉解因为砍掉的都是“注定无解”或者“不可能更优”的分支。但这里有个关键点剪枝判断一定要比继续深搜便宜得多。如果为了剪枝每次都要做很复杂的计算那还不如不剪因为总开销可能更大。我见过有人为了剪枝写了个特别长的辅助函数结果跑下来比原来还慢这就本末倒置了。2.2 剪枝的三个基本原则我总结下来剪枝可以分成三大类理解了这三类以后看到任何剪枝思路都能对号入座。第一类是可行性剪枝这个分支继续走下去有没有可能得到合法解如果中间状态已经违反了约束条件那后面不管怎么走都是死路直接剪掉。经典例子是“八皇后问题”你放皇后的时候发现同一列已经有皇后了那这个位置根本不用往下递归直接跳过。八皇后不用可行性剪枝也能解但加了这个剪枝搜索树会小非常多。第二类是最优性剪枝就算这个分支能走通它得到的答案有没有可能比已知的最好答案更好如果不可能剪掉。典型场景是“求最短路径”或者“最小代价”。你已经找到了一条长度为 10 的路径现在从另一个分支往下走走了一半代价已经超过 10 了那这个分支就可以直接放弃因为就算走完也不可能比 10 更小。这类剪枝通常需要维护一个“当前最优答案”以及一个“当前状态的下界估计”。第三类是重复状态剪枝相同的状态前面已经搜过了那后面遇到一模一样的就直接跳过。简单说就是“别做重复的事”。比如在走迷宫时你已经访问过某个坐标了再去访问一次就是绕圈直接不走。这就是DFS/BFS里的 visited 数组本质上也是一种剪枝只是大家默认它属于基本功没往剪枝上想。还有一些场景需要把“位置”加“剩余步数”一起作为状态否则会遇到“来过但走了不同步数”的情况单独用位置判断会误剪。这三类不是互斥的真实做题目时经常叠加使用。但要注意每加一层剪枝都要保证正确性特别是“最优性剪枝”如果下界估计做错了会把本来该要的解也剪掉那问题就大了。3. 常见剪枝策略拆解与实操要点3.1 可行性剪枝别往死胡同里钻可行性剪枝是最容易理解的就是在递归入口处检查当前状态是否还有可能走到答案。写多了你会发现很多题目的可行性剪枝其实就是“提前验证一下剩余的约束还能不能满足”。举一个经典例子把一根绳子切成若干段要求每一段长度都是整数并且正好用完。假设你当前已经拼了一部分剩下还要拼的绳子长度总和是 S而你手上最长的材料长度是 max_len。如果 S 比所有剩余材料中最长的还要长那显然不可能用一段材料去覆盖它这个分支可以直接剪掉。再比如“组合总和”问题给定候选数和一个目标值找出所有和为 target 的组合。朴素DFS是每个数选或不选排列组合爆炸。一个非常有效的剪枝是先把候选数排序递归时如果当前和已经大于 target就 break 掉。因为你已经从大到小排过序后面只会更大没戏了。我看到很多新手在写可行性剪枝时喜欢在递归函数内部去 if 判断“还有没有可能”但判断逻辑写得跟原问题一样复杂。这不行。剪枝判断应当尽量轻量一般是基于当前累积量、剩余可选范围或者某些上下界估计。一句话剪枝要“快、准、狠”快是计算开销小准是判断正确狠是能尽早砍掉。还有一个特别容易犯的错在判断时用了已经被修改的全局状态导致误判。比如你在循环里对数组做了 swap递归前用这个数组判断递归后又没 swap 回来那下一个分支的判断就全错了。所以写剪枝时确保判断所依赖的数据是当前分支一致的状态。3.2 最优性剪枝用上界和下界逼退搜索最优性剪枝常用在“求极值”的题目里。比如“旅行商问题”的简化版给定几个城市和道路找一条最短路径访问所有城市。你从某个城市出发已经走了一段路发现走过的距离已经比当前已知最短路径长了那就没有必要继续走下去因为后面只会累积更长。但光是“已经走了多长”这种剪枝强度往往不够。真正厉害的是估计“剩余路程的最小可能值”也就是下界。如果“当前已走距离 剩余路程下界”已经大于等于已知最优解就可以剪掉。这里有个实际经验下界不用太精确但必须保证是“乐观估计”也就是真实代价一定不会比它小。比如要求剩下必须访问的城市中每个城市到最近未访问城市的距离之和作为下界。这个下界计算起来很快而且确实不超过真实剩余路径长度。剪枝效率就高很多。相反如果你把下界算得太悲观比如直接设为0剪枝就退化成“只判断已走距离”效果就一般了。想一下如果已知最优解是 100当前已走 50剩下下界估计是 0那你还要把剩下全走完才知道 50真实路程可能超过 100如果下界估计是 60那 5060110 已经超过 100直接剪。这就是“上下界剪枝”的威力。实际操作时我会先写一个没有最优性剪枝的版本跑通之后再看瓶颈。如果瓶颈是搜索层数太深就赶紧补上下界估计。补完之后记得用几个小数据验证结果和原来一样防止下界算错导致漏解。3.3 记忆化搜索把算过的结果存下来记忆化搜索和剪枝经常被放在一起聊因为它们都是在减少重复计算。区别在于剪枝是“砍掉不可能的分支”记忆化是“把已经算过的分支结果保存起来下次直接查表”。我举个直观例子计算斐波那契数列。不加记忆的递归是经典的指数级爆炸每次 fib(n) 都要重新算 fib(n-1) 和 fib(n-2)很多子树被反复计算。加一个字典或数组缓存结果后每个 n 只算一次复杂度变成 O(n)。这就是记忆化搜索。在DFS题里记忆化常见的场景是状态由若干参数决定比如当前坐标、剩余步数、当前累计值而下一步结果只依赖这些参数不依赖你是从哪条路走来的。这时候就可以建一个 memo 数组把参数组合作为 key算过就直接返回。要注意的是记忆化搜索要求状态“无后效性”也就是当前状态的价值不受之前路径影响。如果搜索过程有复杂的前置条件比如某些资源的使用情况会改变后续选择那就不能简单用几个坐标做 key必须把资源状态也加进 key否则会出错。我踩过这样的坑迷宫类题目我简单用 (x, y) 做记忆化结果发现同样的坐标用剩余步数不同能到达终点的可能性是不一样的。比如剩余 10 步能到剩余 2 步不能到。如果只记得“这个坐标能到终点”就会直接返回 true导致错误。所以记忆化的 key 要足够完整但也不能太完整不然状态数量爆炸失去了记忆化的意义。这是个权衡。3.4 顺序优化与上下界剪枝让好的分支先走顺序优化不算传统意义上的剪枝但它对剪枝效果影响极大。同样一棵搜索树你遍历子节点的顺序不同找到最优解的时间可能差很多。举个例子背包问题如果先放价值密度大的物品可能很快找到一个较优解这个较优解就能作为“当前最优”的上界帮助剪掉后面很多分支。反过来如果先放价值低的物品后面还没找到高质量的解上界就很差剪枝力度不足。所以我的习惯是在DFS之前先把候选按某种启发式排序。最常见的是“从大到小”排序尤其是涉及和、积、长度这类问题。因为先处理较大的元素能更快填满/超过限制从而触发可行性剪枝在最优性问题里先处理“潜力大”的元素能快速得到一个较好的可行解进而提升上界。另外“上下界剪枝”有个常见做法入口处先算一个“全局上界”作为初始最优值不用等搜索过程中遇到第一个解才更新。比如求最小值你可以先用贪心算一个较优解把 best 设置为这个值。这样搜索一开始就能剪掉很多比贪心解还差的路径。这个技巧我几乎每次写最优性DFS都会用收益非常明显。顺序优化做得好经常能让剪枝效果提升一个量级。尤其是那种“找是否存在可行解”的问题如果先把最受约束的元素先处理可能一开始就走到了正确路径根本不用大规模搜索。这就是所谓的“约束传播”思想虽然这个名字常出现在约束满足问题里但本质就是“把最难搞的先定下来”。4. 完整案例从一道题看剪枝如何落地4.1 题目描述与朴素DFS光讲概念有点虚我拿一个经典题目过一遍完整过程。题目是这样给定 n 根木棍每根长度已知问能否把它们拼成等长的若干个正方形边简化一下就是“能否把所有木棍分成若干组每组总长度相等”。这是经典的“火柴拼正方形”问题的变体特别适合展示剪枝。我们先定义问题有数组 nums长度总和是 total。如果 total 能被 4 整除且每根木棍长度都不超过 side total/4那我们尝试把所有木棍放进 4 个桶里每个桶最终要刚好 side 长。这等价于把木棍分成4组。朴素DFS思路遍历每根木棍尝试把它放进某个桶里。如果某个桶能放下就递归。写成代码大概是def can_make_square(nums): total sum(nums) if total % 4 ! 0: return False side total // 4 nums.sort(reverseTrue) # 先排个序后面剪枝有用 buckets [0] * 4 def dfs(index): if index len(nums): return all(b side for b in buckets) for i in range(4): if buckets[i] nums[index] side: buckets[i] nums[index] if dfs(index 1): return True buckets[i] - nums[index] return False return dfs(0)这段代码对 n 比较小比如 12还能跑。n 到 15 以上4^15 约 10 亿次直接爆炸。我第一次写这个题的时候就是这样小数据过了大数据死活超时才意识到必须加剪枝。4.2 逐步加剪枝的过程与对比第一步先加最基础的可行性剪枝如果当前桶已经满了那你放下一根木棍时就不用再试这个桶另外如果某个桶和上一个桶当前剩余容量一样那这根木棍放进去的效果是等价的跳过重复桶。这一步能省掉不少重复搜索。for i in range(4): if buckets[i] nums[index] side: # 如果当前桶和之前某个桶的剩余量一样跳过避免重复 if i 0 and any(buckets[j] buckets[i] and j i): continue ...这个“跳过等价桶”非常关键。因为四个桶是等价的如果你把同一根木棍放进编号0的桶和编号1的桶只要两个桶当前累计长度一样后续搜索就是完全重复的。不加这个剪枝同样的局面会被反复搜 4! 次。第二步加最优性剪枝的变体如果当前的桶数量中已经出现了空桶而你现在要往空桶里放一根长度正好填满它的木棍但后面还有几根更短的木棍需要放那这根长木棍就不该放空桶因为长木棍必须优先消耗短木棍的灵活性更强。严格说这不算通用最优性剪枝但这类启发式也能提升效率。更通用的做法是加“如果剩余木棍中最长的都无法填满当前空桶”这种检查。第三步排序。我前面说顺序优化很重要这里应该把 nums 从大到小排序。因为先放大木棍容易触发“某个桶放不下”的剪枝减少分支。我实测同一组数据从大到小排序比从小到大快好几倍。第四步再上一个更强的剪枝如果某根木棍长度正好等于某个桶的剩余容量那它必须放进这个空桶而不是尝试其他桶。这个不是严格的剪枝只是贪心地减少尝试次数。在搜索中如果当前桶为空而 nums[index] 正好等于 side那直接把它单独放一个桶然后继续。因为任何其他放法都会导致这个木棍和别的木棍拼在一起不如单独放灵活。加完这些剪枝后我把同一个 n20 的随机测试数据跑了一遍。朴素版本大概需要遍历几千万个状态剪枝后可能几百个状态就出结果了。这个差距非常直观剪枝不是锦上添花而是能不能过题的决定性因素。这里我还想分享一个心得加剪枝要一步步来每加一个都跑一遍测试集确保结果不变。我经常见到有人一次性写完一堆剪枝结果加上后程序一直出错然后调试半天才发现是某个剪枝条件写反了。所以我习惯把剪枝封装成函数或者在调试时用一个开关变量控制方便快速对比。5. 常见问题与排查技巧实录5.1 剪枝剪错了怎么办这是最致命的问题加剪枝之后结果变错了。原因多半是剪枝条件太强把合法解也剪掉了。比如在最优性剪枝中下界估计得不够“乐观”导致你误以为这个分支不会更优其实它有机会。排查方法先把所有剪枝去掉用小数据跑出正确结果然后逐步加回剪枝。每次加一个对比输出。如果哪一次输出和正确结果不一致那就是刚加的这个剪枝有问题。这一步排查非常笨但非常有效比盯着代码猜快得多。我遇到过的情况是某个数组排序后我直接用了“当前剩余总长度小于某个桶的剩余空间”作为剪枝但粗心写成了“小于等于”结果把刚好相等的合法情况也剪掉了。这种边界错误用对比法一眼就能看出来。5.2 递归栈溢出与参数传递问题深度优先搜索跑太深Python 默认递归深度是 1000 左右超过就会 RecursionError。如果搜索层数和 n 一样大n 到几千就会炸。有些情况下可以手动设置递归深度import sys sys.setrecursionlimit(1000000)但这只是治标。如果搜索深度真的大到几万说明你的搜索树本身很大或者状态设计有问题可能需要用迭代法或者改策略。另外还有一个很隐蔽的Python参数传递问题如果递归函数直接往一个默认参数列表里面添加元素比如def dfs(state[])这个列表是全局共享的所有递归调用都会改同一个列表最后回溯时会乱套。正确做法是每次递归都新建列表或者在递归调用前复制。传 list 的时候尤其要小心“引用传递”的坑。5.3 剪枝失效的典型原因有时候你加了剪枝代码也没错但运行时间还是没降下来。常见原因是剪枝位置放错了。比如你在递归进入后才判断“当前状态是否可行”这时候已经递归了一层开销已经产生。如果能在循环外面就预处理一些条件能省则省。还有一类剪枝失效是因为搜索树的形状不适合你用的剪枝。比如你做了排序但没有优先处理约束最强的分支导致好的剪枝条件迟迟无法触发。举个例在八皇后中如果你先尝试前面的列而不是先尝试冲突最小的位置那可行性剪枝虽然正确但触发得太晚搜索空间依然很大。这时候要把“启发式排序”做好让最受限的选项先被尝试。另一个常见原因是状态重复导致同一条路径被反复搜索但你只做了剪枝没有做记忆化。有些题目光是剪枝还不够必须配合 memo 才能真正降复杂度。比如“单词拆分”类问题当前剩余字符串能否被拆分只取决于剩余内容跟你之前怎么拆的没关系这种情况下必须记忆化纯剪枝是没有用的。5.4 调试DFS的两点小技巧我自己调试DFS的时候会用一个 depth 参数在打印时缩进def dfs(index, depth0): print( * depth findex{index}, buckets{buckets})这样能非常直观地看到搜索走了哪些分支是在哪里回溯的哪里被剪了。你甚至可以临时多加一个变量“被剪枝次数”每次剪枝就累加最后输出看看到底剪了多少。如果剪枝次数很少说明你的剪枝条件还没打中要害。另一个技巧是写一个暴力版和小数据对拍。我经常写一个简单的dfs和一个剪枝版dfs_pruned然后随机生成小数据比对它们的结果。只要小数据结果一致我就比较有信心剪枝没剪错然后再把数据加大测性能。这个习惯帮我省下了大量调试时间。最后说点个人的体会剪枝这个东西不是背模板而是要学会“站在搜索的视角看问题”。每次写递归前先问自己三件事这个状态有没有可能无解有没有可能不如当前最优这个状态以前算过没有想清楚这三问剪枝自然就有了。别一上来就堆乱七八糟的条件那样只会把代码弄得很乱还容易出错。如果你刚接触DFS剪枝我建议多拿几道经典题练手比如组合总和、八皇后、火柴拼正方形、数独解算器。每道题都先写裸DFS再一步步加剪枝记录每一步的运行时间变化。这个过程跑完你对剪枝的直觉会比看十篇文章都有用。
