Dynamic programming is a programming paradigm in which we divide a complex problem into smaller sub-problems. We solve these sub-problems and store the results. Whenever we need to recompute the same sub-problem again, we just used our stored results, thus saving us computation time at the expense of using storage space. This technique of caching the results of sub-problems is known as memoization. Therefore, using dynamic programming allows us to speed up our computations by using memoization, and in some cases, it can bring the computational complexity from exponential to linear, as we will see in the following example.
One of the simplest examples of optimization using dynamic programming is computing the nth member of the Fibonacci sequence. Any term in a Fibonacci sequence is the sum of the last two terms, which can be formally defined as follows:
fib(0)=0
fib(1)=1
fib(n)=fib(n-1)+fib(n-2)
Here, fib(n) represents the nth number in the Fibonacci sequence. From the definition, we can easily compute the Fibonacci sequence as: 0, 1, 1, 2, 3, 5, 8, 13.
Now let's say we want to write a function which would return the nth number in the Fibonacci sequence. A simple way to write this function could be to use recursion, as shown in the following code:
def fibonacci(n):
"""
Returns the n-th number in the Fibonacci sequence.
Parameters
----------
n: int
The n-th number in the Fibonacci sequence.
"""
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
In the preceding code, we have a simple if ... else condition, where if n is less than or equal to 1, we return the value of n; otherwise, we use recursion to compute the sum of the previous two numbers in the sequence. Now let's try to determine the number of calls to the fibonacci function for a small n, let's say 5. Our function calls would look something like the following:
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(5) = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
fibonacci(5) = ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))
fibonacci(5) = (((fibonacci(1) + fibonacci(0)) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))
For such a small value of n, we can still see the repetition in the number of calls to the function with the same argument. We can see that fibonacci(1) is being called five times and fibonacci(0) is getting called three times. If we move a level up, we can see that fibonacci(2) is also getting called multiple times. In this case, the computation is still tractable, but for large values of n the run time of this function would grow exponentially; the runtime complexity is given by O(2n). To give an idea of how fast the runtime grows, to compute the 1,000th term in the Fibonacci sequence using this algorithm, we would need more time than the age of our universe on a computer built with all the electrons in our observable universe.
Since we have proved that it is impossible to compute the nth term of the Fibonacci sequence for any moderately large n, we will look at another algorithm that is based on dynamic programming and looks as follows:
cache = {0: 0, 1: 1} # Initialize the first two values.
def fibonacci(n):
"""
Returns the n-th number in the Fibonacci sequence.
Parameters
----------
n: int
The n-th number in the Fibonacci sequence.
"""
try:
return cache[n]
except KeyError:
fib = fibonacci(n-1) + fibonacci(n-2)
cache[n] = fib
return fib
In this case, we are storing the result of each of our calls to the function in a dictionary, which allows us to access it in O(1). Because of this cache, we only need to compute each term of the Fibonacci sequence exactly once. For each call, we first check whether we have already computed the value. If we have already computed it, we directly access it from the dictionary, otherwise we compute the value. The runtime complexity of this algorithm is O(n) since we are computing each term in the sequence exactly once. We can see, therefore, that using dynamic programming facilitates a trade-off between the runtime complexity and memory complexity, and this allows us to bring down the runtime complexity from being exponential to linear.
If we think about the way we have programmed the Fibonacci series, we start with trying to compute the nth number and then compute the values we are missing. This can be thought of as a top-down approach. Another approach could be a bottom-up approach, in which we start by computing the 0th term and then move to the first, second, and so on. The concept of dynamic programming is the same in both cases, but with just a minor difference in how we write the code, shown as follows:
cache = [0, 1] # Initialize with the first two terms of Fibonacci series.
def fibonacci(n):
"""
Returns the n-th number in the Fibonacci sequence.
Parameters
----------
n: int
The n-th number in the Fibonacci sequence.
"""
for i in range(2, n):
cache.append(cache[i-1] + cache[i-2])
return cache[-1]
As you can see, the code in the preceding example is much simpler, and we don't need to check whether we have already computed the values. This works well in problems where we need all the previous values to compute the next value. However, if we don't need all the previous values, we will end up computing unnecessary values with the bottom-up approach.
We will see in the next sections that the inference algorithms in HMMs allow us to use dynamic programming to break the problem into sub-problems, which makes computations tractable.