POJ 2229

==>原题链接

题目概述

把一个数字n划分为 二的次幂 加和的形式，问共有多少种不同的分法。

思路

一开始企图记忆化搜索后来发现思路是错误的，可能会导致重复。

反例：

dp(5) = dp(3) + dp(2) = (1 + 2) + 2

  = dp(4) + dp(1) = (2 + 2) + 1

但这两种显然是同一种。

正确的思路是 为了避免重复，由于2是一个特别的数字——偶数的基，我们尝试将n的加和算式分为只有偶数相加 和 奇偶相加两种情况（纯奇数相加只有1+1+1...的情况，视作奇偶混合的）。

如果n是奇数，那么只能是奇偶混合相加，dp[n] = dp[n-1]，即在n-1的结果上再加1，与n-1的值无异
如果n是偶数，那么可以有奇偶混合 和 纯偶数相加两种，dp[n] = dp[n-1] + dp[n/2] 其中dp[n-1]易理解，dp[n/2]则是为了保证所得结果dp[n/2]为只有偶数的情况，因为无论n/2是否为偶数，n均为偶数。我们按照这样的划分可以保证既不重复，又不缺漏。

实际上这样的划分很具有题目的特性，并不保证是通用思路。更多的依靠列出大量的式子枚举找规律推倒得出递推。
这启发我们在没有思路的情况下大可枚举找规律，找出突破。

代码

#include <stdio.h>
#include <string.h>

const int N = 1000000000;
int dp[1000000 + 10];

int main()
{
    int i;
    int n;

    memset(dp, 0, sizeof(dp));
    freopen("2229.in", "r", stdin);
    scanf("%d", &n);
    dp[1] = 1;
    dp[2] = 2;

    for (i = 3; i <= n; i++)
    {
        if (i & 1)
        {
            dp[i] = dp[i-1] % N;
        }
        else
        {
            dp[i] = dp[i-1] % N + dp[i/2] % N;
        }
    }

    printf("%d\n", dp[n]);

    return 0;
}