POJ 2229 Sumsets

题意: 给出数n, 问用2的幂来凑n，有几种凑法(取后9位)。

对于数字７的例子:
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4 
所以输出为６

我们令dp[i]意义为：数字ｉ的凑法总数。

如果是奇数，直接相当于前面的数字各种凑法序列随便多插个１，所以dp[n]=dp[n-1]
打个比方，dp[6] = 6， 6个凑法序列都多插一个1，就得到了上面例子中凑奇数7的序列

对于偶数ｎ。如果分析凑成n的序列，若这个序列含有１，那么完全可以看成是数n-1的所有序列多插个１得来的，如果它不含１，即序列所有单元都是２的倍数，就相当于dp[n-1]的序列*2对应得来，所以dp[n] = dp[n-1]+dp[n/2]

代码

#include <cstdio>
using namespace std;

const int maxn = 1000005, md = 1e9;
int dp[maxn];

int main() {
    int n;
    scanf("%d", &n);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (i & 1)
            dp[i] = dp[i - 1];
        else
            dp[i] = (dp[i - 1] + dp[i / 2]) % md;
    }
    printf("%d\n", dp[n]);
    return 0;
}

看这个分析还是挺清楚的..关键是怎么正向地分析出这个方法?(经验?..或者是"大多数博客的..显然易得法..")

首先因为后一个序列和前面序列摆法是有关的，大致可以想到是dp。奇数的情况倒还好想，只差1，所以前面的凑法中，各个序列的都加多个1就对应下来了。 偶数的时候分为有1和无1的情况..我一般可能想不到这样分..但是可以换种方法..偶数可以由哪几种情况得来..当然上一个数多插个1可以想到(加一个数字的方法)，还有就是乘法的方法得来