整数拆分

思路

对于一个数字 n，如果 n 是奇数，那么 n 的所有组合方式中一定包含一个 1，那么它和 n-1 的组合方式种数相同，dp[n] = dp[n-1]；

如果 n 是偶数，那么它的组合方式中可能有 1，也可能没有 1，有 1 的组合方式有 dp[n - 1] 种，没有 1 的组合方式有 dp[n/2] 种，因为偶数组合方式除以 2 后的组合方式其实是一样的，dp[n] = dp[n-1] + dp[n/2]

#include <iostream>
using namespace std;

#define mod 1000000000
int dp[1000001];

long f2n(long n){
    dp[1] = 1;
    for (long i = 2; i <= n; i++){
        if (i % 2)
            dp[i] = dp[i - 1];
        else
            dp[i] = (dp[i - 1] + dp[i / 2]) % mod;
    }
    return dp[n];
}

int main(){
    int n;
    while (cin >> n) {
        cout << f2n(n) << endl;
    }
    return 0;
}