AcWing 170. 加成序列 题解（搜索—迭代加深DFS）

AcWing 170. 加成序列
迭代加深的DFS，就是给DFS加一个限制，限制搜索的层数，避免搜索过深，下面代码中加的限制变量就是depth，限制搜索的层数，有点类似于用BFS优化DFS，先把固定层数的所有DFS搜完，找不到答案的话，再允许搜更深层的

#include

using namespace std;

const int N = 110;

int path[N];
bool st[N];
int n;
int depth;

bool dfs(int u, int depth){  //u表示当前搜索到的层数，depth表示最大搜索层数 
	if(u > depth) return false;
	if(path[u - 1] == n) return true;
	
	//这里需要做一下标注为什么st数组的初始化要在搜索树的每一个节点，而不是在搜索树的depth变动时 
	//下面两个for循环将每个节点前面的所有情况都会处理一遍，所以在每个节点对st进行初始化是可行的
	//为什么在depth变动时是不可行的，因为depth变动之前，搜索树的各枝对st的影响是等效的，就会导致各枝的搜索结果相互影响
	//这个数可能在A枝未用，但是在B枝已用，但是在搜到A枝时显示已用，就会影响接下来的搜索结果 
	memset(st, 0, sizeof st);
	for(int i = u - 1; i >= 0; i -- ){
		for(int j = i; j >= 0; j -- ){
			int s = path[i] + path[j];
			//剪枝操作，如果当前数已经在序列中出现过，或当前数小于序列中的前一位数，或当前数已经大于n，
			//必然找不到答案，就剪枝 
			if(st[s] || s > n || s <= path[u - 1]) continue;
			st[s] = true;  //当前数可用
			path[u] =  s;  //当前数加入队列中 
			if(dfs(u + 1, depth)) return true;
			st[s] = false;  //恢复现场 
		}
	}
	return false;
}

int main()
{
	path[0] = 1;
	while(cin>>n, n){
		
		depth = 1;  //最大搜索层数 
		while(!dfs(1, depth)) depth ++ ;
		for(int i = 0; i < depth; i ++ ) cout<