题解 | #整数拆分#

01背包问题

状态转移表示f[i][j] = f[i-1][j] + f[i][j-a[i]]

本题需要内存优化，进行降维处理 if(j > a[i]) f[j] += f[j-a[i]];

#include<iostream>
using namespace std;
const int n = 25;
const int m = 1e6+10;
typedef long LL;
const LL p =  1000000000;
LL a[n];
LL f[m];
int main(){
    int nn;
    cin>>nn;
    LL index = 1;
    int cnt = 1;
    while(index <= nn){
        a[cnt++] = index;

        index *= 2;
    }
    
    f[0] = 1;
    for(int i = 1;i <= cnt-1;i++){
        for(int j = 0;j <= nn;j++)
        {
            if(j >= a[i])
                f[j] = (f[j] + f[j-a[i]])%p;
        }
    }
    cout<<f[nn];
    return 0;
}