记忆化搜索

#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;
}