算法提高之加成序列

• 核心思想：迭代加深 + dfs

  • 从上往下逐渐增大depth 这样下面没有用的方案就不用遍历了
  • 

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 110;
    
    int n;
    int path[N];
    //当前求哪个位置,最大深度
    bool dfs(int u,int depth)
    {
        if(u == depth) return path[u-1] == n;
        
        bool st[N] = {false};
        for(int i=u-1;i>=0;i--)  //从后往前找
            for(int j=u-1;j>=0;j--)
            {
                int s = path[i] + path[j];
                if(s >= path[u-1] && s<=n && !st[s])
                {
                    st[s] = true;
                    path[u] = s;
                    if(dfs(u+1,depth)) return true;
                }
            }
        return false;
    }
    int main()
    {
        while(cin>>n,n)
        {
            int depth = 1;
            path[0] = 1;
            while(!dfs(1,depth)) depth++;
            
            for(int i=0;i<depth;i++) cout<<path[i]<<" ";
            cout<<endl;
        }
    }