完全背包问题求方案数

例题：AcWing 1371.货币系统

算法分析：
每种物品可以选任意个，求方案总数，就是完全背包问题
求方案数的完全背包方程：
$f[i][j] = \sum\limits_{j=w[i]}^Nf[i][j-w[i]]$ 这里 w[i] 相当于 2 的次幂

最后转化为一维即可，注意顺序（亲测不转化会爆内存，2e7 大概 80M）

转化为这道题目：
一维：$f[j] = \sum\limits_{j=i}^Nf[j-i]$

#include <iostream>

using namespace std;

const int N=1000010;
const int MOD=1e9;

int a[N];
int n,f[N];

int main()
{
    cin>>n;

    f[0]=1;
    for(int i=1;i<=n;i*=2)
    {
        for(int j=i;j<=n;j++)
        {
            f[j]=(f[j]+f[j-i])%MOD;
        }
    }

    cout<<f[n]<<endl;

    return 0;
}

写成背包的形式是这样
$f[j] = \sum\limits_{j=w[i]}^Nf[j-w[i]]$

#include <iostream>
#include <cmath>

using namespace std;

const int N=1000010;
const int MOD=1e9;

int w[N];
int n,f[N];

int main()
{
    cin>>n;
    for(int i=1;i<=21;i++) w[i]=pow(2,i-1);

    int res=0;
    f[0]=1;
    for(int i=1;i<=21;i++) //每种物品
    {
        for(int j=w[i];j<=n;j++) //价值
        {
            if(j>=w[i]) f[j]=(f[j]+f[j-w[i]])%MOD;
        }
    }

    cout<<f[n]<<endl;

    return 0;
}