An example of dynamic programming using fibonacci

memoization-example.cpp

#include <iostream>
#include <cstdlib>
#include <unordered_map>
#include <exception>
#include <string>

namespace
{
  
  using ulli = unsigned long long;

  template <typename T1, typename T2>
  using omap = std::unordered_map<T1,T2>;
  omap<ulli, ulli> solutions;

  template <typename T>
  using conref = const T&;

  template <typename T>
  inline std::ostream& operator<<(std::ostream& strm, std::pair<T,T> pa) noexcept
  {
    return strm << pa.first << ' ' << pa.second;
  }

  template <typename T>
  inline auto print (T t) noexcept
  {
    std::cout << t << std::endl;
  }

  template <>
  inline auto print (bool t) noexcept
  {
    std::cout << std::boolalpha << t << std::endl;
  }

  template <typename T1, typename T2>
  auto getOrElse (conref<omap<T1,T2> > map, conref<T1> key, conref<T2> returnThis) noexcept
  {
    try
    {
      return map.at(key);
    }

    catch (std::out_of_range e)
    {
      return returnThis;
    }

    catch (std::exception e)
    {
      std::cerr << "Unkown error: " << e.what() << std::endl;
      exit(EXIT_FAILURE);      
    }
  }

  template <typename T1, typename T2>
  auto isPresent (conref<omap<T1,T2> > map, conref<T1> key) noexcept
  {
    try
    {
      map.at(key);
      return true;
    }

    catch (std::out_of_range e)
    {
      return false;
    }

    catch (std::exception e)
    {
      std::cerr << "Unkown error: " << e.what() << std::endl;
      exit(EXIT_FAILURE);      
    }
  }

  template std::ostream& operator<<(std::ostream&, std::pair<ulli,ulli>) noexcept;
  template auto print (std::pair<ulli,ulli>) noexcept;
  template auto getOrElse (conref<omap<ulli,ulli> >, conref<ulli>, conref<ulli>) noexcept;
  template auto isPresent (conref<omap<ulli,ulli> >, conref<ulli>) noexcept;

  inline auto fibNoMemo (conref<ulli> arg) noexcept
  {
    if (arg == 0ull)
    {
      return 0ull;
    }

    if (arg == 1ull)
    {
      return 1ull;
    }

    return fibNoMemo(arg - 1ull) + fibNoMemo(arg - 2ull);
  }

  inline auto fibMemo (conref<ulli> arg) noexcept
  {
    if (isPresent(solutions, arg))
    {
      return solutions[arg];
    }

    if (arg == 0ull)
    {
      solutions.insert({0ull, 0ull});
      return 0ull;
    }

    if (arg == 1ull)
    {
      solutions.insert({1ull, 1ull});
      return 1ull;
    }

    solutions.insert({arg, fibMemo(arg - 1ull) + fibMemo(arg - 2ull)});
    return solutions[arg];
  }

  inline auto fibDriver (conref<ulli> arg, conref<bool> memo) noexcept
  {
    if (memo)
    {
      return fibMemo(arg);
    }

    return fibNoMemo(arg);
  }

  inline auto getOrDefault (conref<std::string> str, conref<ulli> t) noexcept
  {
    try
    {
      return std::stoull(str);
    }

    catch (std::invalid_argument e)
    {
      return t;
    }

    catch (std::exception e)
    {
      std::cerr << "Unkown error: " << e.what() << std::endl;
      exit(EXIT_FAILURE);      
    }
  }
};

[[noreturn]] int main(int argc, char* argv[])
{
  --argc;
  ++argv;

  if (argc == 0)
  {
    print("usage: <arg> <memo>");
    exit(EXIT_FAILURE);
  }

  auto arg = getOrDefault(argv[0], 0ull);
  auto memo = false;

  if (argc == 2)
  {
    memo = argv[1][0] == '1';
  }

  print(fibDriver(arg, memo));
    
}