【算法笔记】搜索算法优化：如何用记忆化与剪枝让DFS快100倍？

这里搜索的优化主要是对DFS的优化，我们前面也提到过的DFS搜索算法，是通过穷尽所有的可能来找到最优解或者统计合法解的个数。DFS其本质还是暴力枚举答案，当数据量比较大的时候容易TLE，因为其时间复杂度比较高。

Knight、鲲鹏

1170人浏览 · 2025-04-13 21:02:33

Knight、鲲鹏 · 2025-04-13 21:02:33 发布

这里搜索的优化主要是对DFS的优化，我们前面也提到过的DFS搜索算法，是通过穷尽所有的可能来找到最优解或者统计合法解的个数。DFS其本质还是暴力枚举答案，当数据量比较大的时候容易TLE，因为其时间复杂度比较高。

如果对DFS不太熟悉或者忘记的同学可以看看这篇噢：【算法笔记】深度优先算法DFS(保姆级教学，一篇让你搞懂DFS的精髓)_dfs算法-CSDN博客

搜索有很多优化方式，如减小状态空间，记忆化搜索等，统称为剪枝。无论是何种优化方式，其本质都是想办法减少对不合法及重复的答案的枚举。

剪枝可以笼统的分为两大类：最优性/可行性剪枝、记忆化搜索。

一、为什么需要优化搜索算法？

想象你要在一座巨大的迷宫里找出口：

暴力搜索：像无头苍蝇一样乱撞 → 可能几天都走不出去
优化后：带地图+排除死胡同 → 几分钟找到最短路径

核心矛盾：搜索算法的时间复杂度往往是指数级增长（如 O(2^n)），必须优化！

很多时候刷算法题或者打算法比赛时，如果只是暴力DFS的话可能会过不掉噢~

二、记忆化搜索：避免重复计算

因为在搜索中，相同的传入值往往会带来相同的解，那我们就可以用数组来记忆已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。

场景：背英语单词时遇到一个生词，查字典记住意思 → 下次再见时直接回忆，无需再查

算法本质：将已计算的结果缓存，遇到相同子问题时直接查表，不再需要再次重新计算！

1. 经典案例：斐波那契数列

暴力递归（大量重复计算）：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // 计算fib(3)时会重复计算fib(2)
}

当数据量比较小的时候我们这样是可以的，也递归不了多少次，但是当我们数据量大的时候，通过画递归图你会发现很多数其实在前面已经计算过了，不需要再重复算一遍浪费时间。

记忆化优化（时间复杂度从O(2^n)降到O(n)）：

unordered_map<int, int> memo; // 用哈希表缓存结果，当然用bool数组判断也可以，只要能够判断数有没有被计算过就好了，但用map更方便一些

int fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) {       // 检查是否已计算过，计算过则直接返回
        return memo[n];
    }
    int res = fib(n-1) + fib(n-2);
    memo[n] = res;            // 存储计算结果，方便一下次查看
    return res;
}

我们在这里添加了一个小小的改变，我们加入了记忆化数组，保存我们计算过的数，当下一次需要这个数的时候我们直接调用之前计算的值，就不需要再重复算一次了！！

2. 模板代码

3. 适用场景

存在大量重复子问题（如动态规划）
状态可被唯一标识（如棋盘位置、剩余金额）

三、剪枝操作：提前终止无效搜索

在搜索中导致运行慢的原因有一种是在当前解已经比已有解更差，或者可明确判断出当前解不合法时仍然在搜索，那么我们只需要判断一下当前解是否已经差于已有解或者当前解是否合法即可。

场景：网购时筛选商品：

不剪枝：浏览所有商品 → 耗时
剪枝后：设置价格区间、品牌 → 快速排除不符合条件的商品

算法本质：在搜索过程中，提前跳过不可能达到目标的路径

1. 经典案例：组合总和问题

题目：从 [2,3,6,7] 中找和为7的组合（每个数可重复使用）

未剪枝的DFS：会尝试无效路径如 [2,2,2,2]（和=8 >7）

剪枝优化：排序后，当当前和超过目标时立即返回

vector<vector<int>> result; // 存所有答案
vector<int> currentPath;    // 存当前路径

// 递归搜索函数
void search(vector<int>& nums, int target, int start) {
    // 满足条件：当前和等于目标
    if (target == 0) {
        result.push_back(currentPath);
        return;
    }
    
    // 遍历所有选择
    for (int i = start; i < nums.size(); i++) {
        if (nums[i] > target) 
            break; // 剪枝：后面的数更大，直接停止
        
        currentPath.push_back(nums[i]); // 选择当前数
        search(nums, target - nums[i], i); // 递归搜索（注意还是从i开始）
        currentPath.pop_back();          // 撤销选择
    }
}

// 主函数，通过二维vector开二维数组
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end()); // 关键！必须先排序
    search(nums, target, 0);        // 开始搜索
    return result;
}

2. 模板代码（通用DFS剪枝）

3. 剪枝类型

可行性剪枝：当前路径明显不可能达成目标（如和超过目标值）
最优性剪枝：当前路径已比已知最优解差（如路径更长）
对称性剪枝：排除重复等价状态（如排列中[1,2]和[2,1]视为相同）

四、避坑指南

1. 记忆化搜索常见错误

错误1：缓存了带有副作用的函数（如修改全局变量）
解决：确保函数是纯函数（输入相同 → 输出必然相同）
错误2：状态设计不合理导致漏存关键参数
示例：在递归时漏掉影响结果的参数（如当前索引位置）

2. 剪枝操作常见错误

过度剪枝：错误的条件导致漏掉有效解
检测方法：用小规模测试用例验证
剪枝条件顺序错误
正确顺序：先判断终止条件，再剪枝（避免提前终止）

五、性能对比

方法	时间复杂度	空间复杂度	适用场景
暴力搜索	O(2^n) ~ O(n!)	O(n)	小规模问题
记忆化搜索	O(n) ~ O(n^2)	O(n)	存在重复子问题
剪枝优化	降低常数倍数	O(n)	可提前判断无效路径

六、例题讲解

P1025 [NOIP 2001 提高组] 数的划分 - 洛谷

解题思路：剪枝优化

int n, k;
int ans;

void dfs(int last, int step, int sum) { //上一个位置选择的数，本次要给step位置选择的数，前面选择的数之和
    if (step > k) { //一定不能将step>k&&sum==n一起写在if判断中，因为当step>k时不满足sum==n也需要返回，不满足条件
        if(sum==n)ans++;
        return;
    }
    for (int i = last; i <= n - k + 1; i++) {
        if (sum + i * (k - step + 1) > n)break; //剪枝操作，如果当前这个数的后面全部都选当前这个数，如果这样都
        //大于我们的目标值n，那后面比i大的就一定不满足要求，就不用去递归枚举了
        dfs(i, step + 1, sum + i);
    }
}

void solve() {
    cin >> n >> k;
    dfs(1, 1, 0);
    cout << ans;
}

P1464 Function - 洛谷

解题思路：记忆化搜索

#include <cstdio>
#define LL long long
using namespace std; 
LL dp[25][25][25];

LL w(LL a, LL b, LL c)
{
	if(a <= 0 || b <= 0 || c <= 0) return 1;//两个特判，题意里都有的。
	if(a > 20 || b > 20 || c > 20) return w(20, 20, 20);
	
	if(a <b && b < c)//情况一，每一个没有储存过的“w”值全部储存，如果有就直接调用。
	{
		if(dp[a][b][c-1] == 0)
		{
			dp[a][b][c-1] = w(a, b, c-1);
		}
		if(dp[a][b-1][c-1] == 0)
		{
			dp[a][b-1][c-1] = w(a, b-1 ,c-1);
		}
		if(dp[a][b-1][c] == 0)
		{
			dp[a][b-1][c] = w(a, b-1, c);
		}
		dp[a][b][c] = dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c];
	}
	
	else//同上
	{
		if(dp[a-1][b][c] == 0)
		{
			dp[a-1][b][c] = w(a-1, b, c);
		}
		if(dp[a-1][b-1][c] == 0)
		{
			dp[a-1][b-1][c] = w(a-1, b-1 ,c);
		}
		if(dp[a-1][b][c-1] == 0)
		{
			dp[a-1][b][c-1] = w(a-1, b, c-1);
		}
		if(dp[a-1][b-1][c-1] == 0)
		{
			dp[a-1][b-1][c-1] = w(a-1, b-1, c-1);
		}
		dp[a][b][c] = dp[a-1][b][c] + dp[a-1][b][c-1] + dp[a-1][b-1][c] - dp[a-1][b-1][c-1];
	}
	
	return dp[a][b][c];
}

int main()
{
	LL a, b, c;
	
	while(scanf("%lld%lld%lld", &a, &b, &c))//无限输入，直到“-1 -1 -1”
	{
		if(a == -1 && b == -1 && c == -1) return 0;//-1 -1 -1就直接结束，不运算了。
		
		printf("w(%lld, %lld, %lld) = ", a, b, c);
		printf("%lld\n", w(a, b, c));
	}
}