Introduction

Dynamic Programming is basically used to resolve problems by dividing them into sub-problems. You will begin with the smallest first and then continue with bigger ones. It has been introduced by Richard Bellman in the 50s.

When should we use it ?

When we have optimal structure and overlapping subproblems :

• Optimal structure means that you can break a problem down into smaller and smaller problems and then combine those together to get the optimal solution
• Overlapping subproblems means that we are computing the same thing more than once and dynamic programming works by caching those values so that we don’t actually have to recompute multiple times but once.

Example with Fibonacci sequence

Introduction

If you don’t know one the most famous mathematical sequence here is a little explanation.

The sequence and formula goes like:

The sequence starts with 1 and 1 and then, as you can observe, each term is the sum of the previous two terms in the sequence. So, it’s 1+2, 2+3 2+3, 3+5, 5+8, 8+13, … until the end.

To show how to use Dynamic Programming, we will try with different approaches. We will write a function which will return the referred number of the Fibonacci sequence.

For example if we have a function called fib(n) and “n” equals 1, the function must return the first number of the sequence (so “1).

Or f(5) must return the fifth number of the sequence so “3”.

Recursion Solution

With a recursion approach we will have the following code. It’s pretty naive :

This will work for a small parameter. But as it is not optimized at all, it will failed for large numbers.

Indeed, if we draw a tree of how many times the fib function is called here is what we have :

Recursion Solution with Memoize (storing intermediate results)

One way to decrease the number of steps would be to store the intermediate result in a array. So that we don’t have to repeat those computations each time we face a known call.

For example the first time we call fib(2), we store this value in an array. Next time fib(2) is called, we take the value in the array instead of calculating it.

This is a better way but we can do even better with a bottom-up solution !

Bottom-up Solution

With a bottom-up approach, we will in a sense explicitly build the “memo” array, from left to right from scratch instead of building it recursively as we did in the last example ?

So here is the bottom-up code which will give us the best result :

As you can see, the bottom_up array is initialized manually.

We have the best result because we have avoided all recursions and loops we could!

Indeed, in a first time we have broken our initial problem into sub-problems and then we found the better way to avoid doing the same stuff multiple times.