algorithmic_thinking.cpp

/**
 *  if n >= 2 => f(n) = f(n - 1) + f(n - 2)
 *  else 1
 *
 *  f(30) = f(29) + f(28)
 *  f(29) = f(28) + f(27)
 *
 *  f(3) = f(2) + f(1) (1 + 1) => 2
 *  f(2) = 1
 *  f(1) = 1
 *
 *  1, 1, 2, 3, ...
 */

#include <iostream>
#include <unordered_map>

using namespace std;

/**
 * O(n) space
 * O(n!) time
 */
int fib(int n)
{
  if (n >= 2) {
    return fib(n - 1) + fib(n - 2);
  }
  return 1;
}

/**
 * O(n) space
 * O(n) time
 */
unordered_map<int, int> memo;
int fib_memo(int n)
{
  auto iter = memo.find(n);
  if (iter != memo.end()) {
    return iter->second;
  }

  int value;
  if (n >= 2) {
    value = fib_memo(n - 1) + fib_memo(n - 2);
  } else {
    value = 1;
  }
  memo[n] = value;
  return value;
}

/**
 * O(1) space
 * O(n) time
 */
int fib_optimized_memo(int n)
{
  int a = 1;
  int b = 1;
  int c = 1;
  for (int i = 1; i < n; ++i) {
    c = a + b;
    a = b;
    b = c;
  }
  return c;
}

// 1836311903
int main()
{
  cout << fib_optimized_memo(45) << endl;
}