Dynamic programming basics

We know one beautiful and intuitive algorithmic problem-solving method: recursion. This method divides a problem into smaller, similar subproblems. We call the same function with different parameters until base conditions solve those subproblems. However, often this process solves the same subproblem multiple times, which costs us valuable time and resources. To overcome this issue, you can use dynamic programming, which not only breaks down a problem into subproblems, but also saves and reuses its solutions.

This approach will be the main subject of discussion in this topic. Let's start with formulating a simple problem and then apply the dynamic programming approach to solve it.

A painful scenario

Bob, a Math student, must solve a difficult problem set. To solve the first problem, he uses a calculator to calculate intermediate values. After solving the first problem, Bob smiles and turns the page. But Bob's smile vanishes after reading the second problem. Alas! Since he didn't record the intermediate values from the first problem, he has to calculate most of them again! In Science and Math classes, we all have this experience. Calculating the same values repeatedly is tedious. Same for computers. Although they don't feel emotional pain from such labor, they require more time to solve the same problems multiple times.

What should Bob do? Write down all calculated intermediate values. Same for computers. We should store all results a computer might need again in its memory. Let's explore the concept more deeply by calculating some Fibonacci numbers and analyzing the process carefully.

Brief introduction to the problem

The Fibonacci numbers represent a sequence, the first element of which is $0$, the second is $1$, and each following element is the sum of the previous two. Below are the first eight elements of the sequence:

$0, 1, 1, 2, 3, 5, 8, 13, ...$

For convenience, we will denote the $n^{th}$ element of the sequence as $F_n$. For example, $F_0= 0$ , $F_1= 1$ , $F_6 = 8$ . Given a number $n$, our task will be to calculate $F_n$. Now, let's have a look at a simple solution:

function fib(n):
    if n < 2:
        return n

    return fib(n-1) + fib(n-2)

The algorithm is correct and beautiful. The key line for recursion is the last one: return $fib(n-1) + fib(n-2)$. But calling the same function twice is also alarming. Let's see how this line kills our program's performance.

Let us walk through the computation of the fourth Fibonacci number. The $fib(4)$ function will call $fib(3)$ and $fib(2)$, as shown in the figure below. Afterward, $fib(3)$ will call $fib(2)$, $fib(1)$, and $fib(2)$ will call $fib(1)$, $fib(0)$. Eventually, the following tree will emerge:

Here, the blocks with a yellow background are the repetitive calls. The figure shows that recursively calling a function itself twice will raise our complexity to $2^n$. Clearly, calling this function for large $n$ will exhaust our resources.

Let's look at the figure again. Here, we are calling $fib(2)$ and $fib(0)$ two times each, and $fib(1)$ three times. It is much like reinventing the wheel, i.e., solving the same problem repeatedly, which will always kill our program's performance. In a programming language, we define the situation by saying that our problem has overlapping subproblems.

How can we overcome such situations in programming? The solution comes in the following section.

Memoization

Dynamic programming solves this unpleasant problem. The main strategy of dynamic programming is that we must save all results that we might need again. This technique is called memoization. The memoization-enhanced pseudocode is below:

function fib(n):
    //Create an array to store results
    numbers = array[0, n]
    
    //Initially assign -1 to each element of the array
    for i in [0, n]:
        numbers[i] = -1

    //Call fib_helper to calculate the Fibonacci number 
    return fib_helper(n, numbers)

function fib_helper(n, numbers):

    //If number[n] is not equal to -1, we have already calculated the result. 
    //Return the result from the "numbers" array
    if numbers[n] != -1:
        return numbers[n]

    //Else calculate the Fibonacci number either by the base condition or by recursion
    if n < 2:
        numbers[n] = n
    else:
        numbers[n] = fib_helper(n-1, numbers) + fib_helper(n-2, numbers)

    //At this point we have calculated all Fibonacci numbers from 1 to n, 
    //and stored them in the array "numbers"
    //Return our desired Fibonacci number
    return numbers[n]

In the $fib$ function, we create an array $numbers$ to store the answers for subproblems. Initially, we assign $−1$ to each array element, indicating that the element is not calculated yet. Next, we call the $fib\_helper$ with $n$ and the $numbers$ array as parameters.

The first condition in the $fib\_helper$ function is the very place where memoization starts working: we check if the current number $n$ is already calculated, and if so, we immediately return it as an answer. Otherwise, we calculate, save, and return this number.

Now, take a look at the diagram below representing our recursive calls:

Each arrow's number indicates recursive calls. The blocks with the unchanged $numbers$ array has the light blue background. In step $3$, we calculate the $1^{st}$ Fibonacci number using the base case and store it in the numbers array at index $1$. After that, in step $4$, we call the $fib\_helper$ function with our updated $numbers$ array where we use the base case again to find the $0^{th}$ Fibonacci number. We have represented the block with a dark blue background, indicating that we have an updated $numbers$ array, but it doesn't have our solution. After updating the $0^{th}$ element in step $4$, the program solves the subproblem of finding the $2^{nd}$ Fibonacci number and stores the result at index $2$.

Next, in step $5$, we have an updated array containing the Fibonacci number from $0$ to $2$. This time memoization becomes effective. We immediately return the $1^{st}$ Fibonacci number from the numbers array. Memoization-solved blocks are green. Next, the algorithm calculates and stores the $3^{rd}$ Fibonacci number. Again, in step $6$, memoization solves the last Fibonacci number.

Since each number is calculated exactly once here, the algorithm works in $O(n)$, where $n$ is the number of Fibonacci numbers to calculate. Thus, this procedure is more effective, and this is what we call dynamic programming — when you can optimize the performance of a program by remembering solutions to subtasks.

When to become dynamic?

We must identify our problem before applying dynamic programming. Like the Fibonacci problem, dynamic programming only requires overlapping subproblems. When our program solves the same subproblem multiple times, it has overlapping subproblems and should be rewritten using dynamic programming techniques. However, if the number of overlaps is insignificant compared to the overall computations, then it is advisable not to use dynamic programming since it will increase space complexity.

Conclusion

The dynamic programming steps are listed below:

1. Check if the problem meets the requirement of being a dynamic programming problem;

2. Define a formula to find the solution from the sub-solutions;

3. Solve smaller problems and store the solutions;

4. Use the stored solutions whenever the subproblems reappear.

By following these steps, you can reduce the complexity of a program from exponential to linear. Thus, dynamic programming is a very convenient and necessary tool in a programmer's toolbox, since it greatly improves performance.