Algorithms, C++

My dynamic programming journey [1] – Fib with memorization

It is rather complicated to consider the advance level of dynamic programming at the beginning, so I have decided to start with a basic example: finding Fibonacci numbers.

Since the concepts of recursion and memorization are often required in dynamic programming, therefore, I have implemented a version of memorization.

  1. Set base case of 0 and 1 equal to 1
  2. Check if fib(n) already exist in the array
  3. If yes, return it directly
  4. If no, return it as fib(n-1) + fib(n-2) like ordinary approach

 

Console output:

It can be observed that starting from fib(2), we have obtained the result and store it into the table, which give O(1) future access time.