I was reading an article on Wikipedia about memoization, so I wanted to try and apply it. I am fairly new to this subject, so I thought I'd start small. Does the program use memoization correctly? Is there anything that I can improve?
#include <iostream>
int fibonacci(int num, int* memoize);
int main()
{
int num;
std::cout << "i: ";
std:: cin >> num;
// i will assume that num > 2, just to keep it short and simple
int* memoize = new int[num + 1];
memoize[0] = 0;
memoize[1] = 1;
// -1 indicates that the value is not within the array
for (int i = 2; i <= num; i++)
memoize[i] = -1;
std::cout << num << "th fibonacci number: " << fibonacci(num, memoize) << std::endl;
delete [] memoize;
return 0;
}
int fibonacci(int num, int* memoize)
{
// if value has not been calculated yet
if (memoize[num] == -1)
{
// calculate it and store it in the array
memoize[num] = fibonacci(num - 1, memoize) + fibonacci(num - 2, memoize);
}
return memoize[num];
}
I read that the recursive solution to fibonacci is not preferred, but I am still trying to figure out the iterative solution.