【搜索】dfs（回溯、剪枝、记忆化）

在这里插入图片描述

个人主页：Guiat
归属专栏：我讲你听

在这里插入图片描述

文章目录

1. dfs 回溯
- 1.1 回溯介绍
- 1.2 回溯模板
- 1.3 回溯经典题目
2. dfs 剪枝
- 2.1 剪枝介绍
- 2. 2 剪枝模板
- 2.3 经典题目
3. dfs 记忆化
- 3.1 记忆化介绍
- 3.2 记忆化示例

正文

1. dfs 回溯

1.1 回溯介绍

核心思想：通过试错的方式探索所有可能得解，当发现当前路径无法得到有效解时，撤销（回溯）最近一步的选择，尝试其他分支。
关键步骤
- 选择：在当前步骤做出一个选择。
- 递归：基于这个选择进入下一层决策。
- 撤销（回溯）：如果当前路径不满足条件，回退到上一步，尝试其他选择。

【注】实际上，回溯算法比较灵活，需要具体情况具体分析。

1.2 回溯模板

【求 1 ~ n 的全排列】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1e5 + 10;
int n, a[N]; bool vis[N];// 回溯
void dfs(int deep)
{if (deep == n + 1){for (int i = 1; i <= n; i ++) cout << a[i] << " \n"[i == n];return ;}for (int i = 1; i <= n; i ++){if (vis[i]) continue;vis[i] = true; a[deep] = i;dfs(deep + 1); vis[i] = false;}
}void solve()
{cin >> n; dfs(1);
}int main()
{IOS; int _ = 1; // cin >> _;while (_ --) solve();return 0;
}

1.3 回溯经典题目

【题目】N 皇后

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 30;
int n, ans; bool vis[N][N];void dfs(int deep)
{if (deep == n + 1) { ans ++; return ; }for (int i = 1; i <= n; i ++){if (vis[0][i] || vis[1][deep + i] || vis[2][deep - i + n]) continue;// 修改状态vis[0][i] = true;vis[1][deep + i] = true;vis[2][deep - i + n] = true;dfs(deep + 1);// 恢复现场vis[0][i] = false;vis[1][deep + i] = false;vis[2][deep - i + n] = false;}
}void solve()
{cin >> n; dfs(1); cout << ans << '\n';
}int main()
{IOS;int _ = 1; // cin >>  _;while (_ --) solve();return 0;
}

2. dfs 剪枝

2.1 剪枝介绍

因为搜索过程构成了一棵树，剔除不必要的部分，就像是在树上将树枝剪掉，故名剪枝。
核心思想：通过某些条件或规则，提前终止某些不可能产生最优解的分支，从而减少不必要的计算。
剪枝是回溯法的一种重要优化手段。

2. 2 剪枝模板

void backtracking(参数)
{if (终止条件){存储结果;  // 找到一个有效解return;}for (选择 : 所有可能的选择){if (剪枝条件) continue;  // 跳过当前选择，进行剪枝做出选择;  // 处理当前选择backtracking(新参数);  // 递归进入下一层撤销选择;  // 回溯，撤销当前选择}
}

2.3 经典题目

【题目】数字王国之军训排队

【AC_Code】

#include <iostream>
#include <vector>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 15;
int n, a[N]; vector<int> vec[N];bool dfs(int deep, int cnt)
{if (deep == n + 1) return true;for (int i = 0; i < cnt; i ++){bool flag = false;for (const auto &num : vec[i]){if (a[deep] % num == 0) { flag = true; break; }}if (flag) continue;vec[i].push_back(a[deep]);if (dfs(deep + 1, cnt)) return true;// 恢复现场vec[i].pop_back(); }return false;
}void solve()
{cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i];sort(a + 1, a + n + 1);for (int cnt =  1; cnt <= n; cnt ++){if (dfs(1, cnt)) { cout << cnt << '\n'; break; }}
}int main()
{IOS;int _ = 1; // cin >>  _;while (_ --) solve();return 0;
}

3. dfs 记忆化

3.1 记忆化介绍

记忆化是一种优化技术，主要用于加速递归算法或动态规划算法。
核心思想：通过缓存（或"记忆"）已经计算过的结果，避免重复计算，从而减少算法的运行时间。

3.2 记忆化示例

【计算斐波那契数列】

#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const ll N = 1e5 + 10, p = 1e9 + 7, inf = 1e9; ll dp[N];ll fun(int n)
{if (n <= 2) return 1;if (dp[n] != -1) return dp[n];return dp[n] = (fun(n - 1) + fun(n - 2)) % p;
}void solve()
{memset(dp, -1, sizeof dp); int n; cin >> n; cout << fun(n) << '\n';
}int main()
{IOS;int _ = 1; // cin >>  _;while (_ --) solve();return 0;
}