题解 | #整数拆分#

#include <iostream>
using namespace std;

int dp[1000001];

int main() {
    int n;
    dp[0] = 1;
    for(int i = 1; i < 1000001; i++){
        if(i % 2 == 1){ //i为奇数，能拆分出一个1
            dp[i] = dp[i - 1];
        }else{ //i为偶数，能拆出一个1，或者一个2
            /*
                假设m = i / 2
                那么只用再来一份构成m的组合就是构成i的组合
                所以构成i的组合和构成m的是一样的
            */
            dp[i] = (dp[i - 1] + dp[i / 2]) % 1000000000;
        }
    }
    while (scanf("%d", &n) != EOF) { // 注意 while 处理多个 case
        printf("%d\n", dp[n] % 1000000000);
    }
}
// 64 位输出请用 printf("%lld")