#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::vector;

int fibonacci(int);

int fibonacci(int num, vector<int>& memoizeF);

int main()  {
	int num;

	std::cout << "i: ";
	std::cin >> num;

	// assume num > 2, to keep it short and simple
	//int* memoize = new int[num + 1]; //you can do this with pointers...
	vector<int> memoizeF;
	memoizeF.push_back(0);
	memoizeF.push_back(1);

	// Load the rest of the vector with "not yet written" flags
	// -1 indicates that the value is not within the array
	for (int i = 2; i <= num; i++)
		memoizeF.push_back(-1);

	//std::cout << num << "th fibonacci number: " << fibonacci(num, memoizeF) << std::endl;
	std::cout << num << "th fibonacci number: " << fibonacci(num) << std::endl;
	//delete[] memoize;  //if you allocate memory using the the pointer method, free it up
	return 0;
}


int fibonacci(int num, vector<int>& memoizeF) // int* memoize)
{
	// if value has not been calculated yet
	if (memoizeF[num] == -1)
	{
		// calculate it and store it in the array
		memoizeF[num] = fibonacci(num - 1, memoizeF) + fibonacci(num - 2, memoizeF);
	}

	return memoizeF[num];
}

int fibonacci(int n) {
	if (n == 0 || n == 1) return n;
	else return fibonacci(n - 1) + fibonacci(n - 2);
}