递归值函数调用自身;
一、DFS的介绍
- 概念很简单,但是还是得了解一下,下面介绍的内容是重点
vector<int> vecMap[100010];
// n条边(这个结点所连接的结点) 邻接表建图
for (int i = 0; i < n; ++i) {
int x, y;
vecMap[x].push_back(y);
vecMap[y].push_back(x); //若是无向图就加上这一句
}
(2)图的DFS实现模板
// 假设这是个无向图
// 这里用DFS搜索所有的点(不是边)
// x代表搜到的当前的点
// 开一个搜索数组(标记)搜到为1,未搜到为0
int visited[100100];
void dfs(int x) {
int i;
visited[x] = 1; // 访问到了当前这个点,要标记为1,否则会陷入死循环
for (i = 0; i < g[x].size(); ++i) {
if (!visited[g[x][i]]) {
// 若这个点的邻接点没有访问过(能走)就往这个邻接点走(递归这个邻接点)
// 中间可以做一些其他的 *** 作
dfs(g[x][i]);
}
}
}
- 比如连通块问题;
- 树形DP
树(边数 = 顶点数 - 1 的图)的DFS
- 关于树,它是一个很特殊的图;
- 树更直观,它有层次有深度,也就是说
- 只要我们搜索的时候,搜到的不是该结点的父节点,那么就意味着我们没有搜过这个点
- 那我们就可以不用开标记数组了,在每一个递归的时候,把父节点一起传进去
- pr :父节点,也可以说是这个结点的前一个结点
void dfs(int x, int pr) {
// x为当前传入的结点
for (int i = 0; i < g[x].size(); ++i) {
if (g[x][i] != pr) dfs(g[x][i], x);
}
}
二、使用DFS代替状压枚举: 1. 数位染色DFS写法
#include
using namespace std;
#define ll long long
ll sum;
ll x;
int getSum (ll x) {
int res = 0;
while (x) {
res += x % 10;
x /= 10;
}
return res;
}
int judge = 0; // 找到一个方案数,正好染色的数字之和等于总和的一半,就为true
//x 代表当前这个数字(后面几个已经选过了,还有哪些位置还没有选,
//tmp 代表选了后面几位,我会选到什么 (已经选到的数字的和)
void dfs(ll x, ll tmp) { //12345 取 13
if (x == 0 || tmp * 2 >= sum) {
if (tmp * 2 == sum) {
judge = 1;
}
return ;
}
// 当前x%10的数不取,直接到下一个数
dfs(x / 10, tmp);
// 当前x%10的数取
dfs(x / 10, tmp + x % 10);
}
int main () {
cin >> x; // 输入的数字
sum = getSum(x); // 求位置上的数字的和
dfs(x, 0);
if (judge) cout << "Yes";
else cout << "No";
return 0;
}
2. 记忆化搜索
(1)举个例子:斐波那契数列记忆化搜索,指通过记录已经搜索到的值来降低重复 *** 作次数,从而加快运行速度。
用空间换时间;
拿个数组给它记录过程中的中间值
- 普通递归:O(2^n)
int f(int n) {
if (n <= 1) return 1;
return f(n - 1) + f(n - 2);
}
记忆化搜索:O(n): 在搜索的过程中,把计算过的值用数组或STL容器存储下来,减少重复搜索的时间;这样遇到这个数就可以直接返回其值了
ll dp[100010] = {0};
ll f(ll n) {
if (n <= 1) return dp[n] = 1; //赋值后将这个值返回
if (dp[n]) return dp[n]; // 若记忆数组中有值,就把它返回
return dp[n] = f(n - 1) + f(n - 2);
}
三、分治
将问题拆分成子问题进行求解。
例如:归并排序
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)