被动态规划玩儿坏了。。。

首先说明思路:
每一个数都可以拆成2的次幂的形式,2的次幂有(1,2,4,6,8...),其中只包括一个奇数,那就是1。

假设给定一个数N:
1.N是奇数,那么N拆分的时候必定有一个1,因为2的次幂除了1都是偶数,由很多偶数不可能构成奇数。
所以 f(N)=f(N-1)
举例:
5=(1+4)=(1+2+2)=(1+1+1+2)=(1+1+1+1+1) ;一共有四种拆分形式
4=(4) =(2+2) =(1+1+2) = (1+1+1+1) ;一共四种拆分方式


2.N是偶数,那么可以分成两种情况:
2.1 N中拆分出1,N中拆分出1和上边N是奇数的情况一样,即f(N-1)
举例:
4=(4)=(2+2)=(1+1+2)=(1+1+1+1)
3=(1+2)=(1+1+1)
2.2 N中不拆分出1
不拆分出1,即都是偶数,偶数的性质可知,偶数都可以整除2,假如N的和为2m,那么除2之后变成m,但是并不影响f(N)。
举例:
4=(4)=(2+2) 都不包含1

同理,由2.1和2.2两种情况的结果相加得到完整的4的拆分。
也就是说N为偶数的情况就是f(N)=f(N-1)+f(N/2)---------------好看一点儿就是:f(2m)=f(2m-1)+f(m);


#include<iostream>
using namespace std;
int dp[1000001];
int main(){
    int n;
    dp[0]=1;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            if(i%2==0){
                dp[i]=(dp[i-1]+dp[i/2])%1000000000;
            }else{
                dp[i]=dp[i-1]%1000000000;
            }
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}