题目描述：给你一个数字n，让你构造一个最短 严格递增 的序列a0 ~ ak

a0 = 1, ak = n， 对于 任意 0 < i <= k，都存在 0 =<a， b < i ，有ai = aa ab。

即任意一个数字都能表示成在它前面的某两个数字的和。

解题报告：

搜索， 由于序列长度不会很长，对于每一个长度判断是否可能，第一个可能的长度就是答案。

期中dp[i]表示前面的某2个数字是否能构成i

#include<iostream>
using namespace std;
int n, dp[101], ans[101], len;
bool judge(int deep, int pre)
{
    if (deep == len)
        return dp[n];
    for(int i = pre 1; i < n; i )
    {
        if (dp[i])
        {
            ans[deep] = i;
            int temp[100], cnt = 0;
            for(int j = deep; j >= 0; j--)
                if (ans[j] i <= n && !dp[ans[j] i])
                    dp[ans[j] i] = 1, temp[cnt ] = ans[j] i;
            if (judge(deep 1, i))
                return true;
            for(int j = 0; j < cnt; j )
                dp[temp[j]] = 0;
        }
    }
    return false;
}
int main()
{
    while(scanf("%d", &n) && n)
    {
        if (n == 1)
        {
            printf("1\n");
            continue;
        }
        for(len = 1; 1; len )
        {
            memset(dp, 0, sizeof(dp));
            dp[2] = dp[1] = 1;ans[0] = 1;
            if (judge(1, 1))
                break;
        }
        printf("1");
        for(int i = 1; i < len; i )
            printf(" %d", ans[i]);
        printf(" %d\n", n);
    }
}