文章目录
前言
一、迭代加深
二、AcWing 170. 加成序列
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：迭代加深，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、迭代加深
dfs中的迭代加深和bfs十分的类似，定一个搜索上界，然后利用剪枝去进行优化，进而实现迭代加深
二、AcWing 170. 加成序列
本题链接：AcWing 170. 加成序列
本博客提供本题截图：
本题解析
令一开始的搜索层数为1，如果没有搜到结果的话，我们就让层数++，对应到代码部分为：
int depth = 1; while (!dfs(1, depth)) depth ++;
剪枝部分：我们按照数值最大的部分进行计算，因为这样可以少很多的枝叶，对于冗余部分，用一个st判重数组即可，数组p存的就是答案
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int p[N] = {1}; int n; bool st[N]; bool dfs(int u, int depth) { if (u > depth) return false; if (p[u - 1] == n) return true; memset(st, false, sizeof st); for (int i = u - 1; i >= 0; i -- ) for (int j = i; j >= 0; j -- ) { int s = p[i] + p[j]; if (s > n || s <= p[u - 1] || st[s]) continue; st[s] = true; p[u] = s; if (dfs(u + 1, depth)) return true; } return false; } int main() { while (cin >> n, n) { int depth = 1; while (!dfs(1, depth)) depth ++; for (int i = 0; i < depth; i ++ ) cout << p[i] << ' '; cout << endl; } return 0; }
三、时间复杂度
关于迭代加深的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
