Sometimes in computer science, you will run into problems. You can divide these into subproblems, which can, in turn, be divided into smaller subproblems. If the smaller subproblems overlap, then you can save the result in memory for future reference. This way, you don’t need to compute the same result multiple times, thus increasing the efficiency of the program substantially. This way of solving these problems is referred to as dynamic programming.
In this article, you will learn what dynamic programming is. I will also show how to compute Fibonacci numbers, which is a simple problem that dynamic programming can solve. I will compare the dynamic programming solutions to the naive solution that uses recursion. These examples are written in Python syntax. Finally, I’ll also give some general pointers to keep in mind when attempting to solve problems using dynamic programming
Dynamic programming
What Types of Problems Can Dynamic Programming Solve?
Dynamic programming is typically a way to optimize solutions to certain problems that use recursion. If a recursive solution to a problem has to compute solutions for subproblems with the same inputs repeatedly, then you can optimize it through dynamic programming. As mentioned earlier, in this case, you would simply save the result of the computation for use later if and when it’s needed. This optimization can reduce the time complexity of an algorithm from exponential time to polynomial time. This means that the number of computations n scales like a polynomial expression instead of scaling like an exponential expression as n increases. In general, polynomial expressions grow much slower than exponential expressions.
There are two conditions that need to be satisfied to use dynamic programming:
- Overlapping subproblems
- Optimal substructure property
What Are Overlapping Subproblems?
I alluded to the overlapping subproblems condition earlier. It simply means that when solving the problem in question, the solutions for the same subproblems are repeatedly necessary. In this case, the solutions to these subproblems can be stored for later use to skip recomputation.
Another way to think about this condition is to turn it upside down. If there are no overlapping subproblems, then there’s no point in saving the solutions for the subproblems, and you can’t use dynamic programming.
There are two different ways of storing the solutions to the overlapping subproblems:
- Memoization (top-down)
- Tabulation (bottom-up)
What Is Memoization?
The memoization approach to dynamic programming is very similar to the naive recursion approach, with only a small change. The difference is that we use a lookup table to store solutions to the subproblems, and then use this table to check whether that solution already exists.
If the solution for a certain subproblem already exists in the lookup table, then that solution is returned from the lookup table. If it does not, then it needs to be computed (through recursion) and added to the lookup table.
For the sake of clarity, let’s define a solution for a subproblem in our dynamic programming problem to be DP[X]., with DP[N] being the desired solution and DP[0] being the base solution. In the memoization approach, the program starts from DP[N] and asks for the solutions from which DP[N] can be reached (these should be subproblems of lower order DP[n<N]). Then, from these states, the same process is repeated recursively, until reaching the base solution DP[0].
If this feels a little too abstract, don’t worry. The examples introduced later in this article should clarify what I mean.
Memoization is known as a top-down approach to dynamic programming since the program will start from the desired, last (top) state and work its way down recursively.
What Is Tabulation?
The tabulation approach to dynamic programming works in a reverse manner compared to the memoization approach. The program will start from the base (or bottom) solution for the subproblem and work its way up, solving the subproblems one by one until reaching the desired solution.
In terms of solutions to subproblems, the tabulation approach starts from the base solution DP[0] and then calculates DP[1], DP[2], … DP[N] until reaching the desired solution for the subproblem DP[N]. Since we started from the base solution DP[0] and worked towards the desired solution DP[N], the tabulation approach is also known as a bottom-up approach.
Again, the examples below should make this easier to understand.
What Is Optimal Substructure Property?
If the optimal solution to a problem can be obtained using the optimal solution to its subproblems, then the problem is said to have optimal substructure property.
As an example, let’s consider the problem of finding the shortest path between ‘Start’ and ‘Goal’ nodes in the graph below. The nodes are connected to other nodes via edges, and the distance between two connected nodes is marked with a number next to the edge.
The shortest path from the Start node to the Goal node is through nodes three and four.
This problem clearly has optimal substructure property. Since the shortest path from the Start node to the Goal node goes through Node Four, it clearly follows that this path is a combination of the shortest path from the Start node to Node Four and the shortest path from Node Four to the Goal node.
Many problems do not have optimal substructure property. For example, the problem of finding the longest path (with no cycles) between the Start node and the Goal node in the above graph doesn’t. Here’s how you can see this:
The longest path is: Start - Node Three - Node Two - Node One - Node Four - Goal. However, this does not imply that the longest path from the Start node to Node Two is Start - Node Three - Node Two. The longest path from the Start node to Node Two is actually Start - Node One - Node Four - Node Three - Node Two (and Start - Node One - Node Four - Goal - Node Two, which has equal length to the first one).
Dynamic Programming Example: Calculating Fibonacci Numbers
One of the simplests examples of dynamic programming is the computation of Fibonacci numbers, which are numbers from the Fibonacci sequence. The first Fibonacci number is zero, the second is one, and the subsequent numbers are the sum of the previous two Fibonacci numbers. The 10 first Fibonacci numbers are zero, one, one, two, three, five, eight, 13, 21, and 34.
Let’s first start with the naive, recursive solution. Here’s a Python function to calculate the nth Fibonacci number (indexing starts from zero):
def fib_recursive(n):
if n <= 1:
return n
else:
return fib_recursive(n-1) + fib_recursive(n-2)From this example it is easy to see that this problem satisfies the overlapping subproblems condition since the function clearly has to calculate the previous Fibonacci numbers multiple times (when n > three). The smallest Fibonacci numbers are computed most often, when this function is called for a large n.
This problem also clearly has optimal substructure since there is only a single solution for the subproblems, which are used to compute the solution to the desired problem.
Due to the recursion, this function runs in exponential time.
Let’s next look at how this could be solved using dynamic programming. Let’s start with a top-down solution using memoization. Here’s a Python function that calculates the nth Fibonacci number that implements dynamic programming through memoization:
def fib_DP_memoization(n):
# Define a lookup table
lookup_table = [None] * (n+1)
# Define an inner function for the recursive part
def _inner(n, lookup):
# If the n:th Fibonacci number has not been
# calculated previously, calculate it
if lookup[n] is None:
if n <= 1: # Base case
lookup[n] = n
else:
lookup[n] = _inner(n-1, lookup) \
+ _inner(n-2, lookup)
return lookup[n]
_inner(n, lookup_table)
# Return n:th Fibonacci number
return lookup_table[n]This approach is quite similar to the recursive approach since it starts from calculating the nth Fibonacci number and, in order to calculate it, goes onto calculating the n-1st and n-2nd Fibonacci numbers. The difference is in the lookup table, where the smaller Fibonacci numbers will be saved as they are calculated, so that they do not need to be calculated again and again.
This makes this function actually run in linear time instead of exponential time.
For the sake of an example, let’s also look at a Python function that solves the same problem in a bottom-up manner with dynamic programming using tabulation:
def fib_DP_tabulation(n):
# Define an array and base case(s)
f = [0] * (n+1)
if n > 0:
f[1] = 1
# Calculate Fibonacci numbers bottom-up
for i in range(2, n+1):
f[i] = f[i-1] + f[i-2]
return f[n]In this solution, the nth Fibonacci number is calculated in a bottom-up manner, starting by calculating the first Fibonacci number, then the second, third and so on until reaching the nth Fibonacci number. This function also runs in linear time.
How to Solve Problems Using Dynamic Programming
The first step to solving a problem using dynamic programming is to identify it as a dynamic programming problem. If you can validate that the problem has overlapping subproblems and that it satisfies the optimal substructure property, you can be sure that you can solve it with dynamic programming.
The second step is to decide on a state expression. This state is the set of parameters that uniquely identifies the different subproblems.
In the Fibonacci numbers example, the parameter identifying the state would just be the serial number of a certain Fibonacci number.
There can be more than one parameter identifying a state. You should always use as few parameters as possible, however.
The third — and probably hardest — step in solving problems using dynamic programming is formulating the relation between the different states.
In the Fibonacci number case this is simple, however, since the nth Fibonacci number is the sum of the n-1st and n-2nd Fibonacci numbers. So F[n] = F[n-1] + F[n-2].
The fourth step is to implement memoization or tabulation for the states that you decided upon, using the relation you discovered between the states. This means simply saving the state (or in other words the solution to a certain subproblem) so it can be recovered from memory without recomputation when it is needed again. This should be fairly simple, if you did steps one to three well
