＜＜算法竞赛进阶指南＞＞:加成序列

满足如下条件的序列 X X X（序列中元素被标号为 1 、 2 、 3 … m 1、2、3…m 1、2、3…m ）被称为“加成序列”：

X [ 1 ] = 1 X[1]=1 X[1]=1

X [ m ] = n X[m]=n X[m]=n

X [ 1 ] < X [ 2 ] < … < X [ m − 1 ] < X [ m ] X[1]

对于每个 k k k（ 2 ≤ k ≤ m 2≤k≤m 2≤k≤m）都存在两个整数 i i i 和 j j j （ 1 ≤ i , j ≤ k − 1 1≤i,j≤k−1 1≤i,j≤k−1， i i i 和 j j j 可相等），使得 X [ k ] = X [ i ] + X [ j ] X[k]=X[i]+X[j] X[k]=X[i]+X[j] 。

你的任务是：给定一个整数 n n n，找出符合上述条件的长度 m m m
最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
输入格式
输入包含多组测试用例。
每组测试用例占据一行，包含一个整数 n n n。
当输入为单行的 0 0 0 时，表示输入结束。
输出格式
对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。
每个输出占一行。
数据范围
1 ≤ n ≤ 100 1≤n≤100 1≤n≤100
输入样例：
5
7
12
15
77
0

输出样例：

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

首先观察数据范围 n ≤ 100 n ≤ 100 n≤100, n n n 很小, 然后根据测试数据给出的 n n n 为 77 77 77时,答案也才 9 9 9 , 我们知道迭代加深算法是用于某些深度很深,但是答案的深度很浅情况下求解答案的,我们不难发现,这道题运用的算法就是迭代加深算法, 迭代加深算法的本质就是用 b f s bfs bfs 的思想去写 d f s dfs dfs, 不断的拓展搜索深度, 从 1 1 1 ~ + ∞ +∞ +∞,但是当答案深度较深时,会 t l e tle tle, 在空间开销上远小于 b f s bfs bfs, 在效率上和 b f s bfs bfs 差不多, 但是因为用 d f s dfs dfs 的形式去写,能够进行剪枝,从而大大的提高了搜索效率

对于这道题, 也要进行剪枝和优化
1.优化搜索顺序, 从大到小枚举 i , j i,j i,j, 从而减少搜索分支的数量,从而达到提高效率的目的
2.去除等效冗余, 使用 s t st st 数组判重, 从而减少重复搜索

#include

using namespace std;

const int N = 110;

int path[N], n;

bool dfs(int u, int k)   
{
    if(u == k) return path[u - 1] == n;   //如果最终答案符合题意,则返回true
    
    bool st[N] = {0};  //判重
    
    for(int i = u - 1; i >= 0; i -- )  //因为 j <= i < k 所以从u-1开始枚举
    for(int j = i; j >= 0; j -- )
    {
        int s = path[i] + path[j];     //找到i,j组成k
        if(s > n || st[s] || s <= path[u - 1]) continue;
        //1.越界 
        //2.已经被计算过
        //3.未保持单调性
        st[s] = true;   //标记
        path[u] = s;    //记录路径
        if(dfs(u + 1, k )) return true;   //递归
    }
    
    return false;   
}

int main()
{
    path[0] = 1;
    while(cin >> n, n)   //多组读入
    {
        int k = 1;    //初始化搜索深度
        while(!dfs(1, k)) k ++;    //如果未找到答案,则拓展搜索深度
        
        for(int i = 0; i < k; i ++ ) cout << path[i] << " ";  //打印路径
        cout << 'n';
    }
}