Dynamic programming :

Memoization and tabulation

Let’s observe present both methods by exposing each to the same problem : how to find a specific fibonacci number?

Memoization

First, let’s use recursion to solve this matter.

Ex :

For each iteration

Function fib( ){

Ex : fib 4
===> Find the two previous toms.

Fib 3 fib 2

The result is return at fib(0) or fib(1)
//0 or 1

}

The running time of this recursion would be exponential, with O(2^n)

That’s the opportunity to present the concept of memoization.

It consists in storing results returned by a function, in order to speed up future operations.

Indeed, in different cases, it will allow us to avoid the execution of costly functions , by collecting desired values in constant time.

In this case : white computing the result of fib (3) once, we won’t have to recompute it again during the next iterations.

It allows to drop dramatically the search time.

Indeed, without memoization O(2^n)

With memoization : O(n)

The "tree" is actually traversed only once , and not for every operation.

Memoization follows a “top-down approach". Indeed , we start from the top of the tree , to each node children, to arrive to a leaf node.

Tabulation method

Now, lets check the tabulation method :

This method uses iteration, instead of recursion.

Indeed, we simply need to start by adding 0 at the index 0, and 1 at the index 1.
Then, using an index, at each memory block, simply fompute the addition of the last two blocks. It allows to arrive to the value of n.

On the opposite of memoization , the point is to follow a bottom up approach.
Indeed, we start from 0 or 1, to arrive to the value of n.

Both recursive , or iterative approaches are available to solve such problem.