深度优先搜索：从全排列到记忆化搜索

深度优先搜索DFS的进化之路从全排列到记忆化搜索在算法竞赛中搜索算法是解决问题的基础。然而面对不同类型的问题选用错误的 DFS 模型不仅会导致超时TLE还容易陷入逻辑混乱。本文将以经典的 0-1 背包问题如洛谷 P1048 [NOIP 2005 普及组] 采药为例剖析 DFS 的三种核心形态并总结从暴力搜索到记忆化搜索的进化过程。一、 陷阱排列型 DFS 路线搜索在初学 DFS 时最常接触的是迷宫寻路或全排列问题。这类问题的核心特征是顺序敏感——先采草药 A 再采草药 B与先采 B 再采 A 被视为两条不同的搜索路径。以下是一段典型的错误应用于背包问题的排列型 DFS 代码#includebits/stdc.husingnamespacestd;constintN110;inttmd[N],vl[N],vis[N];intT,M,value0,mv0;voiddfs(intpos,inttime,intv){if(timeT||vmv){valuemax(value,v-vl[pos]);// 试图通过扣除超时物品来回溯答案return;}// 致命的排列枚举for(inti1;iM;i){if(vis[i])continue;vvl[i];timetmd[i];vis[i]1;dfs(i,time,v);v-vl[i];time-tmd[i];vis[i]0;}}失败原因剖析时间复杂度爆炸这种写法试图枚举所有物品的拿取顺序时间复杂度高达O(M!)O(M!)O(M!)。对于M100M100M100的数据必定超时。背包问题只关心“拿了哪些物品的集合”完全不关心拿取的先后顺序。逻辑漏洞在这套逻辑下必须借助极其复杂的边界判断如超时后回退当前物品价值来维持全局最大值极易漏掉合法状态。二、 破局组合型 DFS 子集枚举意识到顺序不重要后DFS 的模型需要从“下一步选哪个物品”转变为“面对当前物品选还是不选”。这就切入了组合型子集型DFS。voiddfs(intpos,inttime,intv){if(posM)return;if(timeT)return;// 只要时间合法随时更新全局最大值valuemax(value,v);// 岔路1选择第 pos1 株草药dfs(pos1,timetmd[pos1],vvl[pos1]);// 岔路2不选第 pos1 株草药dfs(pos1,time,v);}特点去掉了for循环和vis数组每次递归仅产生两个分支。时间复杂度从阶乘级别降维到了指数级别O(2M)O(2^M)O(2M)。虽然逻辑已经完全正确但在M100M100M100时依然会超时因为存在大量重复计算的“残局”。三、 涅槃记忆化搜索 状态型 DFS为了消除组合型 DFS 中的重复计算必须引入“记事本”缓存数组。但在引入记忆化时初学者极易犯下一种将“自顶向下的全局变量”与“自底向上的状态返回值”混用的错误错误示范思维冲突的代码// 试图用全局变量配合 table导致逻辑崩盘intdfs(intpos,inttime){intv0;if(posM||timeT)returnv;// 致命错误查到状态后赋值给全局变量并返回 0if(table[pos][time]){valuetable[pos][time];returnv;}vdfs(pos1,time);if(timetmd[pos1]T){vmax(v,dfs(pos1,timetmd[pos1])vl[pos1]);}table[pos][time]v;returnv;}失败原因剖析记忆化的核心在于状态的无后效性和纯粹性。函数dfs(pos, time)必须是一个纯函数它只回答一个客观问题“站在第pos个物品前还剩time时间后续最多能拿多少价值”。一旦混入全局变量value并在读档时返回错误的0整个状态转移树就会断裂。最终 AC 代码纯粹的状态转移彻底抛弃全局最优解变量完全依赖返回值进行推导这是通向动态规划的最后一步。#includebits/stdc.husingnamespacestd;constintN110;inttmd[N],vl[N];intT,M;inttable[N][1200];// 记忆化数组intdfs(intpos,inttime){// 边界情况没有物品可选或时间耗尽后续收益为 0if(posM||timeT)return0;// 读档如果该状态已计算过直接返回答案if(table[pos][time]!-1){returntable[pos][time];}// 岔路1不选当前物品后续收益即为跳过该物品的收益intvdfs(pos1,time);// 岔路2选择当前物品前提是时间足够if(timetmd[pos1]T){// 当前物品价值 消耗时间后的后续最大收益vmax(v,dfs(pos1,timetmd[pos1])vl[pos1]);}// 存档并返回table[pos][time]v;returnv;}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinTM;for(inti1;iM;i){cintmd[i]vl[i];}// 必须将记忆化数组初始化为 -1因为真实最高价值可能为 0memset(table,-1,sizeof(table));coutdfs(0,0)\n;return0;}四、 总结考场上的 DFS 类型选择指南在面对搜索问题时明确 DFS 的类型是避免方向性错误的关键排列型 / 路线型 DFS适用场景走迷宫寻路、TSP旅行商问题、求解全排列。实现特征返回值为void依赖for循环展开搜索树必须使用标记数组vis进行状态隔离与回溯。常伴随全局变量记录结果。代价O(N!)O(N!)O(N!)规模极其受限。组合型 / 子集型 DFS适用场景挑选队员、子集求和、物品不受顺序影响的挑选。实现特征无for循环针对每个元素直接裂变为“选”与“不选”两个分支。通过参数传递当前累积状态。代价O(2N)O(2^N)O(2N)指数级适用于N≤20N \le 20N≤20的小数据。状态型 DFS / 记忆化搜索适用场景背包问题、存在大量重叠子问题、求极值或方案数本质为动态规划的递归实现。实现特征返回值必须为具体数值如int或long long严禁使用全局变量记录当前累积结果。函数首部查表尾部存表状态转移依靠max、min或四则运算完成。代价仅计算独立状态的总数时间复杂度断崖式下降。从迷恋for循环与回溯到掌握“选与不选”的二叉分支再到彻底剥离全局状态实现记忆化这是每一个算法学习者破茧成蝶的必经之路。