题解 | 整数拆分

#include <iostream>
#include <vector>
#define MOD 1000000000
using namespace std;

int countPartitions(int n);

int main() {
    int n;
    scanf("%d",&n);
    printf("%d",countPartitions(n));
}
// 64 位输出请用 printf("%lld")

int countPartitions(int n){
    vector<int> dp(n+1,0);// 定义n个int都为0
    dp[0]=1;// 定义初始情况

    for(int i=1;i<=n;i*=2){
        for(int j=i;j<=n;j++){
            dp[j]=(dp[j]+dp[j-i])%MOD;// 例dp[7]+=dp[3],因为3+4=7
        }
    }
    return dp[n];
}