/****************************************************************************
 * fs3.c
 *
 * Computer Science 50
 * David J. Malan
 *
 * Computes n'th Fibonacci number.
 *
 * Demonstrates dynamic programming (i.e., memoization).
 ***************************************************************************/
       
#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));
}


/*
 * 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)
        return memo[n];
    else
        return (memo[n] = fs(n-1) + fs(n-2));
}