fib_dynamic_programming.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

class Fibonacci
{
private:
  unordered_map<int, long long> cache;

public:
  long long fib(int n)
  {
    if (n == 0 || n == 1)
    {
      return n;
    }

    if (cache.find(n) == cache.end())
    {
      cache[n] = fib(n - 1) + fib(n - 2);
    }

    return cache[n];
  }

  void displayCache() const
  {
    vector<pair<int, long long>> sortedCache(cache.begin(), cache.end());
    sort(sortedCache.begin(), sortedCache.end());

    cout << "Cache contents:" << endl;
    for (const auto &pair : sortedCache)
    {
      cout << "fib(" << pair.first << ") = " << pair.second << endl;
    }
  }
};

int main()
{
  Fibonacci fibonacci;
  cout << fibonacci.fib(50) << endl;

  fibonacci.displayCache();

  return 0;
}