题目大意如下：
一个数列满足下列四种性质
1、a0 = 1
2、•am = n
3、•a0 < a1 < a2 < ... < am-1 < am
4、对于每一个K(1 <= k <= m)，这里有两个数字,i,j，（他们可能相同也可能不同）(0 <= i, j <= k-1)，有ak = ai + aj ；
现在给你一个n，让你构造出一个最短的满足上述四种性质的数列
解题思路：
一开始觉得应该用BFS，因为是求最优解，想把1---n的数字按递增的顺序入队列，然后一个一个的弹出，放在相应的位置。
但是由于每一个位置确定数字的方式种类会变动，所以没有写出来。然后决定用DFS。
前面两条性质基本不用管，重要的是3 4 条性质。尤其是第四条，ak是由ai aj加起来构成，而i j 的范围也已经给出。假设现在
k==2,那么它可以由a0 a1, a1 a1 ,a0 a0,三种形式构成。所以在下标移动的时候，i从0开始，j从k-1开始，j不动，i移动，即可
得出ak的组合情况。
为了满足递增序列条件，每一项我都按照a0+ak-1来构造的，比如，当n==5的时候
a0 a1 a2 a3
1 2 3 4
搜索的思想也就是从这里开始了，构造这个数列有很多步，每一步有很多种可能，处理好K步，然后再处理k+1步，如果不行，那就
返回上一步重新选择可行的方案继续进行。过程中当然也要 用到标记数组起到剪枝的作用。
而题目中最后一个要求是要求最短的，也就是说，当我们找到一种答案的时候还要判断它是不是最短的，如果不是，那么要继续
找，如果是最短的，那么当然就要退出循环。而每次一要开始判定并找寻最短序列的条件，就是当a0+ak-1==n的时候，因为此时
如果出现这个条件，则证明数列已经按基本要求构造完成了，除了最短这个条件之外。
以n==5为例来讲，当知道a0+a3==n的时候，就退出，把a3置0，然后看看三个数值的时候构造的这个数列是否满足要求。如果现在
假设的是三个数值的情况，那么很自然的在1 2 3这个序列中要找到==n的组合。a0+a2==4 a1+a2==5,依据循环可以得到==N的组合，
那么我们也就找到了更短的那个答案序列，接下来要做的就是更新最小长度，然后把现在找的的数列存起来。
之后，我们还是一样的思路，想找更短的，把a2划掉置0,然后a1+a1==4变成a0 a1 a2,我们知道，现在最短的长度是3
那么当前的情况肯定还是要向长度为4的方向搜索的，显然不对了，即使再搜到长度为3的另一种答案我们也不需要了，因为
答案可能不止一种，但是我们只需要求出其中一个就可以了。
所以要加上相应的控制条件。
代码如下：
//Addition Chains //
//题目链接：http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1009&ojid=2&cid=4532&hide=0
/*
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<memory.h>
using namespace std;
int num[11000],temp[11000];
int minlength;
int n;
void dfs(int pos)
{
int t;
int i,j,k;
if(pos>=minlength)
return ;
for(i=0;i<pos;i++)
{
t=num[i]+num[pos-1];
if(t==n)
{
if(pos<minlength)
{
memset(temp,0,sizeof(temp));
minlength=pos;
for(j=0;j<pos;j++)
temp[j]=num[j];
}
return ;
}
if(t<n)
{
num[pos]=t;
dfs(pos+1);
num[pos]=0;
}
}
}
int main()
{
// #ifndef ONLINE_JUDGE
//freopen("f:\\in.txt","r",stdin);
//#endif
int i,j,k;
while(scanf("%d",&n),n)
{
if(n==1)
{
printf("1\n");
continue;
}
memset(num,0,sizeof(num));
memset(temp,0,sizeof(temp));
minlength=999;
temp[0]=num[0]=1;
dfs(1);
for(i=0;i<minlength;i++)
{
if(i==0)
printf("%d",temp[i]);
else
printf(" %d",temp[i]);
}
printf(" %d\n",n);
}
return 0;
}