Dynamic Programming and Memoization(Kotlin Fibonacci Example)

We won’t go much into theory but, you can read all about dynamic programming here. It is an optimization technique in which a complicated problem is broken down into subproblems recursively. Let us take the classical case of the Fibonacci sequence. The Fibonacci sequence is defined by the following formula

fib(1) = 1,
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2).

The sequence is defined such that the Fibonacci of a number is the sum of the two previous terms. We have the base case when the number is 1 and…