算法1

自己的写法，找到f[i]和已经算出的f[]的关系。

#include <iostream>
#include <algorithm>

using namespace std;

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

int n;
int f[N];


int main() {
    cin >> n;
    f[0] = 1;
    f[1] = 1;
    f[2] = 2;
    for(int i = 3; i <= n; i++){
        if(i % 2 == 1){
            f[i] = f[i-1];
        }else{
            f[i] = f[i-1] + f[i/2];
        }
        f[i] %= mod;
    }
    printf("%d\n", f[n]);
    return 0;
}

算法2

看作完全背包问题。

要多看看，没有很理解。

#include <iostream>
#include <algorithm>

using namespace std;

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

int n;
int 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;
        }
    }
    printf("%d\n", f[n]);
    return 0;
}