## Dynamic programming

**Dynamic programming** (DP) is a computer programming method which consists in breaking down a complex problem into smaller problems, usually in a recursive way. Then, these problems are solved one at a time, typically storing the already computed results so as to avoid computing them more than once.

## Dynamic programming and the Fibonacci series

A paradigmal example of a problem which can be solved using DP consists in finding the *n*-th term of the Fibonacci series. The Fibonacci series is defined recursively in the following way:

That is, in order to calculate the value of the *n*-th term of the series F_{𝑛}, we need to know the previous two terms. Thus, a simple recursive approach might be used to solve the problem.

```
def fibonacci_recursive(n):
if n == 0 or n == 1:
return 1
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
```

While correct, this implementation is extremely inefficient. For example, if we try to calculate the fourth value of the series by calling

`fibonacci_recursive(4)`

we do indeed get the correct value F_{4} = 4 . However, this function call with 𝑛 = 4 subsequently causes two recursive calls to the function with arguments 𝑛 -1 = 3 and 𝑛 – 2 = 2 . These, in turn, trigger further recursive calls in order to calculate their value, and so forth until reaching the base cases F_{0} and F_{1}.

The following diagram shows the flow used to compute the previous value, where each box represents a function call.

As we can observe, the function is run a total of 9 times, and there are 4 calculations of non-trivial (that is, not a base case) terms: one for F_{4}, one for F_{3} and two for F_{2}. Indeed, the red boxes show that the non-trivial term F_{2} is needlessly computed twice: once in the calculation of F_{4} in the upper level, and again in the calculation of F_{3}.

Given this setting, the following natural question arises: how can we avoid repetitive computations to calculate the value of F_{4}? As you might have guessed, this is where dynamic programming comes into play.

We already noted that in order to calculate the *n*-th element of the series we need to calculate the two previous terms. By induction, it follows that we need to calculate *all * the terms of the sequence up to the *n*-th element in order to calculate its value. Given that we need to compute all the terms of the sequence, consider the following approach: we will start by setting the trivial base cases, and then starting from the first non-trivial term, we will iteratively calculate the following element using the previous two values.

The key point is that each time we calculate a value, we will **keep this value **in our program’s memory, so we can reuse it whenever it is necessary in the future. In the Fibonacci series example, the first non-trivial value we will calculate is F_{2 }. Note that, once this value is computed, we will use it in order to calculate the following term of the series, F_{3 }= F_{1} + F_{2} , and also in the next one, F_{4} = F_{2} + F_{3 }. Therefore, despite being used twice, by saving it in memory we can **compute it only once.**

## Implementation example of a dynamic programming approach

Here is an example of the implementation of a dynamic programming approach to solve the problem of finding the *n*-th term of the Fibonacci series:

```
import numpy as np
def fibonacci_dp(n):
if n == 0 or n == 1:
return 1
last_value = 1
current_value = 1
for i in range(n-1):
aux_value = current_value
current_value += last_value
last_value = aux_value
return current_value
```

Although this function looks more complex than the fibonacci_recursive above, it is in fact much more optimal. In particular, it involves only n-1 non-trivial calculations which correspond to the calculation of terms F_{2} , F_{3} , … , F_{𝑛 }, one time each. This is in contrast with the naive recursive approach, which involves a number of calculations which grows exponentially with *𝑛 .*

For example, in the case of calculating F_{5}, only 4 calculations are needed, while 7 would be needed using the recursive function. For F_{10} , just 9 calculations are used instead of 88. If we calculated F_{50} , using the DP approach we would need just 49 sums, while the recursive approach would require 20,365,011,073 calculations!

## Conclusion

This simple example illustrates the importance of choosing an efficient way to tackle a problem, even when there are different alternatives yielding the same result. This is particularly key when the problem has a recursive nature requiring the use of previously computed values. In this case, we saw that by just storing these values using a dynamic programming approach, overhead is dramatically reduced, especially as the number of nested calculations increases.

In future posts we will show how to apply a dynamic programming model to solve the problem of pricing in hotels. In particular, we will use it for calculating the optimal price to be set a number of days before the date of stay, in order to maximize benefits in the long run.

**If you found this post useful, we invite you to share it with your** **contacts . See you in social networks!**