题解 | #整数拆分#

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    int dp[1000001];
    dp[1] = 1;
    dp[2] = 2;
    while (cin >> n) {
        for (int i = 3; i <= 1000001 ; 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;
    }
}

就是找到dp的规律就行