算法基础篇：（十八）从超时到秒过！DFS 优化指南：剪枝 + 记忆化让暴力搜索 “脱胎换骨”

前言

在算法世界里，深度优先搜索（DFS）就像一位 “万能探险家”—— 无论是枚举子集、破解数独，还是解决八皇后这类经典难题，它都能凭着 “穷举一切” 的韧性找到答案。但这位探险家也有个致命缺点：一旦遇到稍大的数据规模，就会陷入 “盲目绕路” 的困境，最终因超时被淘汰。 其实，DFS 的效率瓶颈并非无法突破。真正的算法高手，都懂得用 “剪枝” 为搜索树 “瘦身”，用 “记忆化” 为重复路径 “存档”。今天这篇指南，就带大家全面解锁 DFS 优化的核心玩法，从基础原理到实战案例，从入门到进阶，让你的 DFS 从 “暴力莽夫” 变身 “智慧探险家”，轻松应对各类难题！下面就让我们正式开始吧！

一、为什么 DFS 需要优化？—— 从一个 “超时惨案” 说起

先来看一个直观案例：计算斐波那契数 F (30)。如果用最朴素的递归实现：

int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n-1) + fib(n-2);
}

看似简单的代码，背后却藏着巨大的效率黑洞。计算 F (30) 时，需要重复计算 F (28)、F (27)、F (26)…… 甚至 F (1) 会被计算上百万次！时间复杂度呈指数级增长（O (2ⁿ)），F (40) 就能让程序卡到 “无响应”。

再比如 “数的划分” 问题：将 200 分成 6 份，不考虑顺序。无优化的 DFS 会枚举所有可能的组合（包括 1+1+…+198 这类无效路径），搜索树规模大到惊人。

这些 “超时惨案” 的根源，本质上是 DFS 的 “暴力枚举” 特性：

1. 无效路径过多：很多分支明显不可能得到解，却仍被强行探索。
2. 重复计算严重：大量相同的子问题被反复求解，浪费算力。
3. 搜索顺序混乱：优先探索低效路径，迟迟找不到有效解或最优解。

而优化的核心，就是针对这三大痛点，用 “剪枝” 砍掉无效路径，用 “记忆化” 缓存重复结果，用 “搜索顺序优化” 引导 DFS 走 “捷径”。

二、剪枝：给搜索树 “砍枝”，告别无效探索

剪枝的本质，就像探险家在迷宫里遇到死胡同就立刻回头，看到绕远路就果断放弃。它通过提前识别无效分支，减少不必要的计算，让搜索树 “瘦” 下来。

下面介绍 4 种最常用的剪枝技巧，每种技巧都结合实战案例和 C++ 代码，让你既能懂原理，又能直接落地。

2.1 排除等效冗余：避免 “换汤不换药” 的重复路径

2.1.1 原理剖析

等效冗余是指搜索树中存在多条 “结果相同但路径不同” 的分支。比如组合问题中，{1,2,3} 和 {3,2,1} 是同一个组合；数的划分中，1+2+5 和 5+2+1 是同一种分法。这些分支本质上是 “换汤不换药”，只需探索一条即可。

排除等效冗余的核心思路：给搜索加 “顺序约束”，强制路径按固定规则生成，从源头避免重复。

2.1.2 实战案例：组合型枚举（洛谷 P10448）

题目描述：

从 1~n 中选 m 个整数，按字典序输出所有组合（同一组合内升序，不同组合按字典序排序）。

输入：5 3

输出：1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5

优化思路

组合问题的核心是 “顺序无关”，因此我们强制要求：每次选择的元素必须大于上一次选择的元素（用begin参数控制）。这样一来，{2,1,3} 这类逆序组合就不会被生成，直接砍掉所有等效冗余分支。

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> path;  // 记录当前组合

// begin：当前选择的起始位置（避免重复）
void dfs(int begin) {
    // 递归终止：已选够m个元素
    if (path.size() == m) {
        for (auto x : path) cout << x << " ";
        cout << endl;
        return;
    }
    // 从begin开始枚举，确保元素递增
    for (int i = begin; i <= n; i++) {
        path.push_back(i);
        dfs(i + 1);  // 下一次选择必须大于当前元素
        path.pop_back();  // 回溯：恢复现场
    }
}

int main() {
    cin >> n >> m;
    dfs(1);
    return 0;
}

代码解析

• begin参数是关键：它限制了每次枚举的起始位置，比如选了 2 之后，下次只能从 3 开始，避免出现 2→1 的逆序。
• 对比无优化版本（从 1 开始枚举所有元素，再判断是否已选），该版本的搜索树规模从 O (nᵐ) 骤减到 O (C (n,m))（组合数），效率提升呈指数级。

2.2 可行性剪枝：提前预判 “死胡同”

2.2.1 原理剖析

可行性剪枝是指：在搜索过程中，根据问题的约束条件，判断当前路径是否有可能得到合法解。如果不可能，就直接终止该分支，避免 “一条路走到黑”。

比如爬山时看到前方是悬崖，就不会继续往前走；解题时发现 “剩余资源不够完成任务”，就不会再探索该路径。可行性剪枝的核心是 “提前预判”，用约束条件卡住无效路径。

2.2.2 实战案例：数的划分（洛谷 P1025）

题目描述：将整数 n 分成 k 份，每份不能为空，不考虑顺序，求不同的分法数。

输入：7 3

输出：4（1+1+5、1+2+4、1+3+3、2+2+3）

题目链接：https://www.luogu.com.cn/problem/P1025

优化思路

约束条件有两个：

1. 每份不能为空（即每次选择的数≥1）。
2. 不考虑顺序（每份数≥前一份，排除等效冗余）。

可行性判断：假设当前已选 c 份，总和为 sum，剩余 k-c 份。如果sum + begin*(k-c) > n，说明即使剩余每份都选最小的begin，总和也会超过 n，该路径无效，直接剪枝。

C++ 代码实现

#include <iostream>
using namespace std;

int n, k;
int sum = 0;    // 当前已选数的总和
int ans = 0;    // 合法分法数

// pos：已分的份数；begin：当前选择的最小数（避免冗余）
void dfs(int pos, int begin) {
    // 已分完k份，判断是否等于n
    if (pos == k) {
        if (sum == n) ans++;
        return;
    }
    // 枚举当前可能的数（从begin开始，避免冗余）
    for (int i = begin; i <= n; i++) {
        // 可行性剪枝：剩余份数*最小数 > 剩余总和，直接终止
        if (sum + i * (k - pos) > n) break;
        sum += i;
        dfs(pos + 1, i);  // 下一份数≥当前数
        sum -= i;          // 回溯
    }
}

int main() {
    cin >> n >> k;
    dfs(0, 1);
    cout << ans << endl;
    return 0;
}

代码解析

• 剪枝核心：if (sum + i * (k - pos) > n) break;比如当前 sum=3，pos=1（已分 1 份），k=3（还需分 2 份），i=3。剩余总和需≤7-3=4，而 2 份最小为 3+3=6>4，因此该分支无效，直接 break。
• 该剪枝让搜索树的无效分支大幅减少，对于 n=200、k=6 的测试用例，无剪枝版本可能超时，而剪枝后可瞬间得出结果。

2.3 最优性剪枝：追求 “更快更好”，拒绝 “画蛇添足”

2.3.1 原理剖析

最优性剪枝适用于最优化问题（如求最小值、最大值）。其核心思路是：

1. 记录当前找到的最优解（如最少缆车数、最短路径）。
2. 在搜索过程中，如果当前分支的代价已超过已知最优解，说明该分支不可能得到更优解，直接剪枝。

比如找最少缆车数时，已知最优解是 2 辆，而当前已用了 3 辆，就没必要继续探索该分支 —— 再怎么搜，也不可能比 2 辆更少。

2.3.2 实战案例：小猫爬山（洛谷 P10483）

题目描述：N 只小猫坐索道下山，每辆缆车最大承重量为 W，每只小猫重量为 C_i。求最少需要多少辆缆车。

输入：5 19961 2 1994 12 29

输出：2（1994+2=1996，1+12+29=42，共 2 辆）

题目链接：https://www.luogu.com.cn/problem/P10483

优化思路

1. 最优性剪枝：记录当前最少缆车数ret，如果当前使用的缆车数cnt ≥ ret，直接剪枝。
2. 可行性剪枝：如果某只小猫的重量 + 当前缆车总重 > W，不能放入该缆车。
3. 搜索顺序优化：先安排重量大的小猫 —— 大猫能快速填满缆车，尽早找到较优解，为后续剪枝提供更严格的条件。

C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20;
int n, W;
int C[N];          // 小猫重量
int cnt = 0;       // 当前使用的缆车数
int car_load[N];   // 每辆缆车的当前总重
int ret = N;       // 最优解（初始化为最大可能值）

// 按重量从大到小排序，优化搜索顺序
bool cmp(int a, int b) {
    return a > b;
}

void dfs(int pos) {
    // 最优性剪枝：当前缆车数≥已知最优解，直接返回
    if (cnt >= ret) return;
    // 所有小猫都安排完毕，更新最优解
    if (pos > n) {
        ret = cnt;
        return;
    }
    // 尝试将当前小猫放入已有的缆车
    for (int i = 1; i <= cnt; i++) {
        if (car_load[i] + C[pos] <= W) {  // 可行性剪枝
            car_load[i] += C[pos];
            dfs(pos + 1);
            car_load[i] -= C[pos];  // 回溯
        }
    }
    // 新租一辆缆车
    cnt++;
    car_load[cnt] = C[pos];
    dfs(pos + 1);
    // 回溯
    car_load[cnt] = 0;
    cnt--;
}

int main() {
    cin >> n >> W;
    for (int i = 1; i <= n; i++) cin >> C[i];
    sort(C + 1, C + 1 + n, cmp);  // 先安排大猫
    dfs(1);
    cout << ret << endl;
    return 0;
}

代码解析

• 最优性剪枝是核心：if (cnt >= ret) return; 一旦当前缆车数超过已知最优解，直接终止该分支，避免无效计算。
• 搜索顺序优化的作用：先安排 1994（最大的猫），它只能单独占一辆缆车，后续小猫再填充剩余空间，能快速找到 “2 辆” 这个最优解，让后续分支的剪枝更有效。
• 对比无剪枝版本，该代码在 N=18 时仍能快速运行，而无剪枝版本可能需要数分钟甚至更久

2.4 优化搜索顺序：让 “好路” 先出现，加速收敛

2.4.1 原理剖析

搜索顺序对 DFS 效率的影响，堪比 “选择走高速还是乡间小路”。同样的目的地，走高速能更快到达；同样的问题，选对搜索顺序能大幅减少分支。

优化搜索顺序的核心原则：优先探索约束强、可能性小的分支。这样能尽早找到有效解或最优解，为后续剪枝（尤其是最优性剪枝）提供更严格的条件。

2.4.2 实战案例：八皇后问题（洛谷 P1219）

题目描述：在 n×n 棋盘上放 n 个皇后，使每行、每列、每条对角线上只有一个皇后。输出前 3 个解和总解数。

输入：6

输出：2 4 6 1 3 53 6 2 5 1 44 1 5 2 6 34

优化思路

1. 约束条件：每行、每列、两条对角线只能有一个皇后。
2. 搜索顺序优化：按行搜索，每行只放一个皇后 —— 这样天然避免了行冲突，减少了约束判断。
3. 可行性剪枝：用三个数组标记列、主对角线、副对角线是否被占用，不满足条件的列直接跳过。

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

const int N = 15;
int n;
bool col[N];         // 标记列是否被占用
bool diag1[N * 2];   // 主对角线（y - x + n）：避免负索引
bool diag2[N * 2];   // 副对角线（y + x）
int ans = 0;         // 解的总数
vector<int> path;    // 记录当前解（path[x]表示第x行皇后的列号）

void dfs(int x) {
    // 所有行都放完，记录解
    if (x > n) {
        ans++;
        if (ans <= 3) {  // 输出前3个解
            for (auto y : path) cout << y << " ";
            cout << endl;
        }
        return;
    }
    // 枚举当前行的每一列
    for (int y = 1; y <= n; y++) {
        // 可行性剪枝：列或对角线已被占用，跳过
        if (col[y] || diag1[y - x + n] || diag2[y + x]) continue;
        // 标记占用
        col[y] = diag1[y - x + n] = diag2[y + x] = true;
        path.push_back(y);
        dfs(x + 1);
        // 回溯：取消标记
        path.pop_back();
        col[y] = diag1[y - x + n] = diag2[y + x] = false;
    }
}

int main() {
    cin >> n;
    dfs(1);
    cout << ans << endl;
    return 0;
}

代码解析

• 搜索顺序优化：按行搜索（x 从 1 到 n），每行只放一个皇后，无需判断行冲突，减少了 1/3 的约束检查。
• 可行性剪枝：通过col、diag1、diag2快速判断列和对角线是否被占用，时间复杂度 O (1)。
• 对比 “按列搜索” 或 “随机位置搜索”，该顺序能让搜索树的分支数大幅减少，对于 n=13 的测试用例，仍能在秒级内得出结果。

三、记忆化搜索：给重复路径 “存档”，避免重复计算

如果说剪枝是 “砍无效路径”，那记忆化搜索就是 “存重复结果”。它针对 DFS 中大量重复的子问题，用 “备忘录” 缓存第一次计算的结果，后续遇到相同子问题时直接读取，无需重新计算 —— 本质上是 “空间换时间” 的终极策略。

3.1 原理剖析：从 “重复计算” 到 “一次存档”

以斐波那契数 F (5) 为例，无记忆化的递归会重复计算 F (4)、F (3)、F (2)…… 甚至 F (1) 被计算上百次。而记忆化搜索会：

1. 第一次计算 F (2) 时，将结果存入备忘录（如memo[2] = 1）。
2. 后续再需要 F (2) 时，直接从备忘录读取，无需重新递归。

记忆化搜索的核心是：识别重复子问题，用备忘录缓存结果。它保留了 DFS 的递归结构，又避免了重复计算，是解决 “重叠子问题” 的利器。

3.2 实战案例 1：斐波那契数（力扣 509）

题目描述：F (0)=0，F (1)=1，F (n)=F (n-1)+F (n-2)（n>1）。计算 F (n)。

输入：5

输出：5

优化思路

• 用数组memo作为备忘录，memo[n]存储 F (n) 的结果。
• 递归前先检查备忘录：如果已计算，直接返回；否则计算后存入备忘录。

C++ 代码实现

#include <iostream>
#include <cstring>
using namespace std;

class Solution {
private:
    int memo[35];  // 备忘录：存储已计算的斐波那契数
public:
    int fib(int n) {
        memset(memo, -1, sizeof(memo));  // 初始化：-1表示未计算
        return dfs(n);
    }
    
    int dfs(int n) {
        if (memo[n] != -1) return memo[n];  // 已计算，直接读取
        if (n == 0 || n == 1) return memo[n] = n;  // base case：存入备忘录
        // 计算后存入备忘录
        return memo[n] = dfs(n-1) + dfs(n-2);
    }
};

int main() {
    Solution sol;
    int n;
    cin >> n;
    cout << sol.fib(n) << endl;
    return 0;
}

代码解析

• 时间复杂度：从 O (2ⁿ) 骤减到 O (n)—— 每个子问题只计算一次。
• 空间复杂度：O (n)（递归栈 + 备忘录），对于 n=1e5 可能栈溢出，但题目中 n≤30，是完全适用的。
• 对比无记忆化版本，F (40) 的计算时间从 “秒级” 缩短到 “微秒级”。

3.3 实战案例 2：Function（洛谷 P1464）—— 三维记忆化

题目描述：实现递归函数 w (a,b,c)，规则如下：

1. 若 a≤0 或 b≤0 或 c≤0，返回 1。
2. 若 a>20 或 b>20 或 c>20，返回 w (20,20,20)。
3. 若 a<b 且 b<c，返回 w (a,b,c-1)+w (a,b-1,c-1)-w (a,b-1,c)。
4. 否则返回 w (a-1,b,c)+w (a-1,b-1,c)+w (a-1,b,c-1)-w (a-1,b-1,c-1)。

输入：1 1 1；2 2 2；-1 -1 -1

输出：w(1,1,1)=2；w(2,2,2)=4

题目链接：https://www.luogu.com.cn/problem/P1464

问题分析

该函数的递归过程存在大量重复子问题。例如，w (5,5,5) 会多次调用 w (4,4,4)、w (4,4,3) 等 —— 如果不记忆化，当 a、b、c 接近 20 时，递归次数会爆炸式增长，导致超时。

优化思路

• 用三维数组memo[a][b][c]作为备忘录（a、b、c 最大为 20，空间仅 25×25×25=15625，极小）。
• 递归时先检查备忘录，未计算则按规则计算并缓存。

C++ 代码实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 25;
LL memo[N][N][N];  // 三维备忘录

LL dfs(LL a, LL b, LL c) {
    // 规则1：边界条件
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    // 规则2：缩小范围到20以内
    if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);
    // 已计算，直接返回
    if (memo[a][b][c]) return memo[a][b][c];
    // 按规则计算并缓存
    if (a < b && b < c) {
        return memo[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);
    } else {
        return memo[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);
    }
}

int main() {
    LL a, b, c;
    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;
        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c));
    }
    return 0;
}

代码解析

• 三维备忘录的优势：精准缓存每个 (a,b,c) 组合的结果，避免重复计算。
• 空间效率：虽然是三维数组，但规模极小（15625 个 LL 类型，约 125KB），完全不占用内存。
• 时间效率：即使输入 a=15、b=15、c=15，也能瞬间得出结果，而无记忆化版本会超时。

3.4 实战案例 3：滑雪（洛谷 P1434）—— 二维记忆化

题目描述：在 R×C 的高度矩阵中，从某点滑向上下左右相邻点，只能滑向高度更低的点。求最长滑坡长度。

输入：5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

输出：25（从 25 滑到 1，共 25 步）

优化思路

• 暴力枚举：从每个点出发 DFS，计算最长滑坡长度，但会重复计算大量子问题（如从 24 滑到 1 的路径，会被 25、23 等多个起点重复计算）。
• 记忆化优化：用memo[i][j]存储 “以 (i,j) 为起点的最长滑坡长度”，递归时缓存结果。

C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int R, C;
int height[N][N];  // 高度矩阵
int memo[N][N];    // 记忆化数组：memo[i][j]表示以(i,j)为起点的最长滑坡长度
// 上下左右四个方向
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int dfs(int i, int j) {
    if (memo[i][j]) return memo[i][j];  // 已计算，直接返回
    int max_len = 1;  // 至少能滑1步（当前点）
    // 探索四个方向
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k];
        int y = j + dy[k];
        // 边界检查 + 高度检查（只能滑向更低的点）
        if (x >= 1 && x <= R && y >= 1 && y <= C && height[x][y] < height[i][j]) {
            // 递归计算子问题，更新最大长度
            max_len = max(max_len, dfs(x, y) + 1);
        }
    }
    // 缓存结果
    return memo[i][j] = max_len;
}

int main() {
    cin >> R >> C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> height[i][j];
        }
    }
    int ans = 0;
    // 枚举所有起点，找最大值
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            ans = max(ans, dfs(i, j));
        }
    }
    cout << ans << endl;
    return 0;
}

代码解析

• 记忆化的核心：memo[i][j]缓存了以 (i,j) 为起点的最长长度，后续再遇到该点时无需重新递归。
• 时间复杂度：O (R×C)—— 每个点只计算一次，四个方向的探索是常数级。
• 对比暴力版本（O (R×C×4^k)，k 为最大滑坡长度），该版本在 R=100、C=100 时仍能秒过。

四、DFS 优化的核心原则与避坑指南

4.1 核心原则

1. 先判后搜：在进入递归前先做剪枝判断，避免无效递归调用（比如先检查cnt >= ret，再处理子问题）。
2. 精准剪枝：剪枝条件要严格但不 “过度”—— 既不能放过无效分支，也不能误剪有效分支。
3. 空间换时间要适度：记忆化的空间复杂度不能超过题目限制（比如 n=1e5 时，一维数组可行，三维数组则会内存溢出）。
4. 优先优化搜索顺序：搜索顺序对效率的影响往往比剪枝更大，优先探索约束强、可能性小的分支。

4.2 避坑指南

1. 回溯时必须恢复现场：剪枝或记忆化时用到的标记数组（如st、row），递归返回后必须重置，否则会影响后续搜索。
2. 多组数据要重置状态：处理多组测试数据时，标记数组、备忘录必须重新初始化（如memset(st, 0, sizeof(st))）。
3. 避免记忆化数组越界：比如斐波那契数的备忘录大小要覆盖 n 的最大值，避免数组越界。
4. 剪枝条件不能 “画蛇添足”：复杂的剪枝条件本身也需要计算时间，要确保剪枝收益大于计算成本（比如简单的break比复杂的逻辑判断更高效）。

总结

最后，记住一句话：好的算法不是 “暴力枚举”，而是 “有策略地探索”。掌握 DFS 优化，让你的算法能力再上一个台阶！ 如果你在学习过程中遇到了具体问题，或者有更好的优化技巧想要分享，欢迎在评论区留言讨论～