记忆化搜索

#include <iostream>
using namespace std;

const int N = 1010;

int n;
int dp[N];

int f(int x)
{
	if (dp[x]) return dp[x];
	int sum = 1;
	for (int i = 1; i * 2 <= x; i++)
	{
		sum += f(i);
	}
	return dp[x] = sum; // 把之前得到的解决方案保存起来， 减少递归次数
}

void solve()
{
	cin >> n;
	cout << f(n) << endl;
}

int main()
{
	solve();
	return 0;
}

多写几组数据就很好写出递推公式了

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector<int> dp(1000+1,0);
    dp[1]=1;
    for(int i=2;i<=1000;i++){
      if(i%2==1){
        dp[i]=dp[i-1];
      }else{
        dp[i]=dp[i-1]+dp[i/2];
      }
    }
    cout<<dp[n];
    return 0;
}