题解 | #整数拆分#

完全背包变形

（参考高赞回答）

• 第i轮 dp[j]:前i种物品组合成容量恰好为j的方法数
• 递推关系：类比完全背包（优化） dp[j]=dp[j]+dp[j-w[i]]

#include<iostream>
#include<cmath>
using namespace std;

int w[22];
int dp[1000000001];

int best(int sum,int n){
    dp[0]=1;//容量为0时,初始方法数为1
    for(int i=1;i<=sum;i++){//容量为0时,初始方法数为0（注意不是INF）
        dp[i]=0;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=w[i];j<=sum;j++){//从前往后更新
             dp[j]=dp[j]+dp[j-w[i]];
            dp[j]=dp[j]%1000000000;
        }
    }
    return dp[sum];
}

int main(){
    int sum,n;
    while(scanf("%d",&sum)!=EOF){
        for(int i=1;i<=21;i++)w[i]=pow(2,i-1);
        printf("%d\n",best(sum,21));
    }
}