【C++】已通过

需要采用递推，递归和递归+动态规划的方式都会出现一些问题，栈溢出

#include<iostream>
using namespace std;
#define MAXINT 1000000000
#define MAXN 1000000
int mem[MAXN + 1];
int f(int n) {
	for (int i = 2; i <= n; i++) {
		if (i % 2 == 0) {
			mem[i] = (mem[i - 1] + mem[i / 2]) % MAXINT;
		}
		else {
			mem[i] = mem[i - 1];
		}
	}
	return mem[n];
	
}
int main() {
	int N;
	mem[1] = 1;
	while (cin >> N) {
		/*for (int i = 1; i <= N; i++) {
			mem[i] = -1;
		}*/
		cout << f(N)   << endl;
	}
	return 0;
}