全站第一个题解

再仔细思考后，我们会发现：除了i等于1、2、3，其他时候如果i是奇数，那么i / 2不会产生新的数。这时候d[i] = d[i - 1]。如果i是偶数，那么i / 2会产生一个新的数，这时只需要加上d[i / 2]就可以产生新的递推数组。递推式如下：

当i为奇数时：d[i] = d[i - 1]。
当i为偶数时：d[i] = d[i - 1] + d[i / 2]

代码如下:

#include<bits/stdc++.h>
using namespace std;
int d[1005];
int main(){
    d[1] = 1;
    d[2] = 2;
    d[3] = 2;
    int n;
    cin >> n;
    for(int i = 4;i <= n;i ++){
        if(i % 2){
            d[i] = d[i - 1];
        } else {
            d[i] = d[i - 1] + d[i / 2];
        }
    }
    cout << d[n];
    return 0;
}