/****************************************************************************
 * fs4.c
 *
 * Computer Science 50
 * David J. Malan
 *
 * Computes n'th Fibonacci number.
 *
 * Demonstrates dynamic memory allocation.
 ***************************************************************************/
       
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>


// prototype
long long fs(int);

// cache of answers
long long * memo;

// sentinel value indicating absence of a memoized answer
const long long SENTINEL = -1;


int
main(int argc, char * argv[])
{
    int i, n;

    // ensure proper usage
    if (argc != 2)
    {
        printf("Usage: %s n\n", argv[0]);
        return 1;
    }

    // validate n
    n = atoi(argv[1]);
    if (n < 0)
    {
        printf("Input must be non-negative.\n");
        return 1;
    }

    // instantiate memo
    memo = (long long *) malloc((n+1) * sizeof(long long));
    if (memo == NULL)
    {
        printf("Out of memory!\n");
        return 2;
    }

    // initialize memo, using sentinel for answers not yet computed
    memo[0] = 0;
    memo[1] = 1;
    for (i = 2; i <= n; i++)
        memo[i] = SENTINEL;

    // compute and print n'th number in Fibonacci sequence
    printf("fs(%d) = %lld\n", n, fs(n));

    // free up memory
    free(memo);
}


/*
 * long long
 * fs(int n)
 *
 * Returns n'th number in Fibonacci sequence.
 */

long long
fs(int n)
{
    // compute n'th number
    if (memo[n] != SENTINEL)
    {
        printf("Found fs(%d) in memo.\n", n);
        return memo[n];
    }
    else
    {
        memo[n] = fs(n-1) + fs(n-2);
        printf("Computed fs(%d) for first time.\n", n);
        return memo[n];
    }
}