POJ 2229 Sumsets DP

http://poj.org/problem id=2229

题目大意：

将一个数分解为2的幂的和，有多少种方法。如7有6种

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

思路:

看别人的思路的。。。。。。

如果n是奇数，那么其中必须要有一个为1，也就是dp[n]=dp[n-1]；
如果n是偶数,那么有两种情况
有1的情况，那么加上n-1的方法恰好可以变为偶数，所以dp[n-1]
没有1的情况，每个因子都是2的幂，提取一个2出来就是dp[n/2]

#include
  
   
const int MAXN= 1000000+10;
const int mod=1000000000;
int dp[MAXN];
int main()
{
     dp[1]=1;
     dp[2]=2;
     for(int i=3;i
   
    >1])%mod; } int n; while(~scanf("%d",&n)) { printf("%d\n",dp[n]); } return 0; }