Dynamic Programming In Python: Using Fibonacci Sequence

Dynamic programming is a programming method that aims to optimize solutions to problems. It was developed by Richard Bellman in the 1950s and has since become popular. In dynamic programming, we aim to break down a complicated bigger problem into simpler sub-problems in a recursive manner. If in breaking down the problem into sub-problems we encounter those sub-problems again, the problem is said to be overlapping. Then we try to find the optimal solutions to the sub-problems which solutions will then be combined with other sub-problems to get the overall solution. Thereby, the problem is said to have an optimal substructure.

 

Most times when we have solved the smaller sub-problems we store the results of the solution so that when similar sub-problems are encountered, the results can be reused. This concept in dynamic programming is called memoization. Memoization not only speeds up computing, it also saves on computer resources.

In dynamic programming, we will be using the memoization technique a lot.

To illustrate how dynamic programming is used in practice let us take a problem that has both overlapping sub-problems and an optimal substructure. That is the problem of finding the Fibonacci sequence. We will be using the Fibonacci sequence as an example of dynamic programming in python.

The first ten Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Each item in the sequence is derived from the sum of the two previous items except for the case when n is 0 or 1. Then in those instances, when n is 0 the sequence is 0 and when 1 the sequence is 1.

Traditionally, the Fibonacci sequence can simply be solved using a recursive algorithm. Just like the one below:

In the code, lines 4 and 5 are used to state the cases where n is either 0 or 1. Then if n is neither of these, then recursively we call the sum of the previous two Fibonacci numbers.

This solution or algorithm is simple but not elegant. This is because the complexity of the algorithm is exponential. Therefore, it does not scale for large Fibonacci numbers. If you call it on n being 120, it would take more than 250,000 years to finish. Quite some age. Therefore, it would do with some optimization.

Now, let’s see how dynamic programming with python can help.

First, we state that dynamic programming will be applicable when a problem has overlapping sub-problems and that each sub-problem has an optimal solution which will be combined to give the overall solution. That is what we are doing in the above recursive calls. Let’s illustrate it with some pictures. For example when we are looking for the Fibonacci of 6. Look at the number of calls that are generated.

Each call is a sub-problem. You can see that fib 2 was called 5 times while fib 3 was called 3 times before getting the final result. Since we can generate solution for each of the sub-problems, it would be nice to just generate the solution once, an optimal solution for the sub-problem, and use that result for every time that sub-problem was called. The operation of storing this result and using it for subsequent sub-problems is called memoization. Creating a memo of previously encountered problems that was solved.

Using this concept, we can now write a second code for the Fibonacci sequence based on dynamic programming using python.

As you can see from the dynamic programming code above, we are using memoization with a dictionary, fib_dict, to store already known results of sub-problems and these results are called when similar sub-problems are encountered. In line 9 we created the dictionary and gave it the initial values of the Fibonacci sequence. Then in line 11 we called the Fibonacci function, fast_fib. Lines 1 to 7 contains the code for the Fibonacci computing function, fast_fib. In the code, we first check to see if the key, n, is already in the dictionary, if it is, we return it but if it is not we compute the Fibonacci sequence recursively and store the result so that it can be used in subsequent calls. This is done consecutively as any n is needed. Finally, it returns the value for the key, n, in the dictionary where n is the Fibonacci number we are looking for.

This dynamic programming implementation runs in linear time and it scales considerably. I just so love it. It is much better than the earlier recursive Fibonacci code.

I hope you now know how dynamic programming works and how to implement it in other problem spaces.

Happy pythoning.