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

深度优先搜索（DFS）的进化之路：从全排列到记忆化搜索

在算法竞赛中，搜索算法是解决问题的基础。然而，面对不同类型的问题，选用错误的 DFS 模型不仅会导致超时（TLE），还容易陷入逻辑混乱。本文将以经典的 0-1 背包问题（如洛谷 P1048 [NOIP 2005 普及组] 采药）为例，剖析 DFS 的三种核心形态，并总结从暴力搜索到记忆化搜索的进化过程。

一、 陷阱：排列型 DFS （路线搜索）

在初学 DFS 时，最常接触的是迷宫寻路或全排列问题。这类问题的核心特征是顺序敏感——先采草药 A 再采草药 B，与先采 B 再采 A 被视为两条不同的搜索路径。

以下是一段典型的错误应用于背包问题的排列型 DFS 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int tmd[N], vl[N], vis[N];
int T, M, value = 0, mv = 0;

void dfs(int pos, int time, int v) {
if(time > T || v == mv) {
value = max(value, v – vl[pos]); // 试图通过扣除超时物品来回溯答案
return;
}
// 致命的排列枚举
for(int i = 1; i <= M; i++) {
if(vis[i]) continue;
v += vl[i];
time += tmd[i];
vis[i] = 1;
dfs(i, time, v);
v -= vl[i];
time -= tmd[i];
vis[i] = 0;
}
}

失败原因剖析：

二、 破局：组合型 DFS （子集枚举）

意识到顺序不重要后，DFS 的模型需要从“下一步选哪个物品”转变为“面对当前物品，选还是不选”。这就切入了组合型（子集型）DFS。

void dfs(int pos, int time, int v) {
if (pos > M) return;
if (time > T) return;

// 只要时间合法，随时更新全局最大值
value = max(value, v);

// 岔路1：选择第 pos+1 株草药
dfs(pos + 1, time + tmd[pos + 1], v + vl[pos + 1]);
// 岔路2：不选第 pos+1 株草药
dfs(pos + 1, time, v);
}

特点：
去掉了 for 循环和 vis 数组，每次递归仅产生两个分支。时间复杂度从阶乘级别降维到了指数级别 $O(2^M)$。虽然逻辑已经完全正确，但在 $M=100$ 时依然会超时，因为存在大量重复计算的“残局”。

三、 涅槃：记忆化搜索 （状态型 DFS）

为了消除组合型 DFS 中的重复计算，必须引入“记事本”（缓存数组）。但在引入记忆化时，初学者极易犯下一种将“自顶向下的全局变量”与“自底向上的状态返回值”混用的错误：

错误示范：思维冲突的代码

// 试图用全局变量配合 table，导致逻辑崩盘
int dfs(int pos, int time) {
int v = 0;
if(pos > M || time > T) return v;

// 致命错误：查到状态后赋值给全局变量，并返回 0
if(table[pos][time]) {
value = table[pos][time];
return v;
}

v = dfs(pos + 1, time);
if (time + tmd[pos + 1] <= T) {
v = max(v, dfs(pos + 1, time + tmd[pos + 1]) + vl[pos + 1]);
}
table[pos][time] = v;
return v;
}

失败原因剖析：
记忆化的核心在于状态的无后效性和纯粹性。函数 dfs(pos, time) 必须是一个纯函数，它只回答一个客观问题：“站在第 pos 个物品前，还剩 time 时间，后续最多能拿多少价值？”。一旦混入全局变量 value，并在读档时返回错误的 0，整个状态转移树就会断裂。

最终 AC 代码：纯粹的状态转移

彻底抛弃全局最优解变量，完全依赖返回值进行推导，这是通向动态规划的最后一步。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int tmd[N], vl[N];
int T, M;
int table[N][1200]; // 记忆化数组

int dfs(int pos, int time){
// 边界情况：没有物品可选或时间耗尽，后续收益为 0
if(pos > M || time > T) return 0;

// 读档：如果该状态已计算过，直接返回答案
if(table[pos][time] != –1) {
return table[pos][time];
}

// 岔路1：不选当前物品，后续收益即为跳过该物品的收益
int v = dfs(pos + 1, time);

// 岔路2：选择当前物品（前提是时间足够）
if (time + tmd[pos + 1] <= T) {
// 当前物品价值 + 消耗时间后的后续最大收益
v = max(v, dfs(pos + 1, time + tmd[pos + 1]) + vl[pos + 1]);
}

// 存档并返回
table[pos][time] = v;
return v;
}

int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> T >> M;
for(int i = 1; i <= M; i++){
cin >> tmd[i] >> vl[i];
}

// 必须将记忆化数组初始化为 -1，因为真实最高价值可能为 0
memset(table, –1, sizeof(table));

cout << dfs(0, 0) << '\\n';
return 0;
}

四、 总结：考场上的 DFS 类型选择指南

在面对搜索问题时，明确 DFS 的类型是避免方向性错误的关键：

从迷恋 for 循环与回溯，到掌握“选与不选”的二叉分支，再到彻底剥离全局状态实现记忆化，这是每一个算法学习者破茧成蝶的必经之路。