#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

long fib_dp(int n);
long fib_memo(int n);
long fib_rec(int n);

int main(int argc, char **argv)
{
  if (argc < 2 || strlen(argv[1]) == 0 || !isdigit(argv[1][0]))
    {
      fprintf(stderr, "USAGE: %s n\n", argv[0]);
      return 1;
    }

  int n = atoi(argv[1]);
  
  printf("fib(%d) = %ld\n", n, fib_rec(n));
  printf("fib(%d) = %ld\n", n, fib_memo(n));
  printf("fib(%d) = %ld\n", n, fib_dp(n));
}

long fib_rec(int n)
{
  if (n < 2)
    {
      return n;
    }
  else
    {
      return fib_rec(n - 1) + fib_rec(n - 2);
    }
}

long fib_memo_helper(int n, long memo[]);

long fib_memo(int n)
{
  // initialize memo to empty (-1, since we know Fib. number all non-negative)
  long memo[n + 1];
  for (int i = 0; i <= n; i++)
    {
      memo[i] = -1;
    }

  // initialize base cases
  memo[0] = 0;
  memo[1] = 1;

  // call memoized recursive function
  return fib_memo_helper(n, memo);
}

long fib_memo_helper(int n, long memo[])
{
  if (memo[n] != -1)
    {
      // value is already stored in the memo
      return memo[n];
    }
  else
    {
      // recursively calculate value as before
      long fib = fib_memo_helper(n - 1, memo) + fib_memo_helper(n - 2, memo);
      
      // save result in memo before returning
      memo[n] = fib;
      return fib;
    }
}

long fib_dp(int n)
{
  // initialize memo with base cases
  long memo[n + 1];
  memo[0] = 0;
  memo[1] = 1;

  // fill out the rest of the memo
  for (int i = 2; i <= n; i++)
    {
      // apply recurrence, but instead of recursion, get results directly from memo
      memo[i] = memo[i - 1] + memo[i - 2];
    }

  // return entry in memo we're interested in
  return memo[n];
}