常用的递归算法:dfs(深度优先搜索),记忆化搜索,分治

常用的递归算法:dfs(深度优先搜索),记忆化搜索,分治,第1张

递归值函数调用自身;


一、DFS的介绍

  • 概念很简单,但是还是得了解一下,下面介绍的内容是重点
1. 图的DFS (1)先看一下vector是怎么建图的?
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
(3)树的DFS实现模板
树(边数 = 顶点数 - 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);
}

三、分治

将问题拆分成子问题进行求解。


例如:归并排序

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/607241.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-14
下一篇 2022-04-14

发表评论

登录后才能评论

评论列表(0条)

保存