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

long fib_dp(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_dp(n));
}

long fib_dp(int n)
{
  long f[n > 1 ? n + 1 : 2];

  f[0] = 0;
  f[1] = 1;

  for (int i = 2; i <= n; i++) // O(n) iterations
    {
      f[i] = f[i - 1] + f[i - 2]; // O(1) 
    }

  // O(n) overall
  
  return f[n];
}

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