memoization.cpp

/*
    optimization of fibonacci numbers implementation
    time comlexity : O(n) rather than exponential ,as in older recursive implementation.
*/
int fib(int n, int memo[])
{
    if (memo[n] == -1) // if we encounter this number first number, as memo[] is initialized with -1
    {
        int res;
        if (n == 0 || n == 1)
        {
            res = n;
        }
        else
        {
            res = fib(n - 1, memo) + fib(n - 2, memo);
        }
        memo[n] = res;
    }
    return memo[n];
}