IzIy's Files

将一个整数拆分成2的幂相加，比如

4 = 4

4 = 2 + 2

4 = 1 + 1 + 2

4 = 1 + 1 + 1 + 1 奇数情况： f(2n+1) = f(2n)

故只需要算偶数

核心思想在于，想到相邻两个偶数有关系，或者利用已知结果推导进行推导，

已经想到的有，将拆分分成两种情况讨论，即拆分多项式里边有1和没1的情况。

有1的项，必至少有两个1：比如10 = 8 + 1 + 1 故这里只需要等于8的数量。

无1的项，最小的项是2，所以整个项必可以除2，

所以 10 = 5 * 2 这里只需要算等于5的数量。

所以当 f(2n+1) = f(2n)

而f（2n）= f(2n-2) +f(n),利用递推可以很轻松算出结果即：

int f(int i)
{
    if(i%2) return f(i-1);
    if (i == 1) return 1;
    else
    {
        return f(i-2) + f(i/2);
    }
}

此时，函数复杂度为 O(2^n)

f可以优化成非递归的形式，即利用空间数组：

int n[MAX];
n[1] = 1;
for(int i=2; i<MAX; i++)
{
    if(i%2) return n[i] = n[i-1];
    else
    {
        n[i] = n[i-2] + n[i/2];
    }
}