An introduction to dynamic programming

Nine fundamental algorithms to learn how to wield dynamic programming

Dynamic programming is an essential competitive programming technique. It consists in trading off memory for time to avoid repeating computations. This can yield significant improvements in performance, sometimes turning an exponential-time algorithm into a linear one.

This is the first part to a series of article. The first one illustrates the fundamentals of dynamic programming with three basic problems, the second one explores three more advanced algorithms and three separate articles will tackle more complex problems. Here is the list of all the algorithms we’ll cover:

1. Calculating the n-th tribonacci number (part 1)
2. Efficient binomial coefficient calculator (part 1)
3. Counting paths in a grid (part 1)
4. The Rod-Cutting Problem (part 2)
5. Finding a longest-increasing subsequence (part 2)
6. Calculating change (part 2)
7. The Knapsack Problem (part 3)
8. Finding the longest common subsequence (part 4)
9. The Sequence Alignment Problem (part 5)

I tried to make it as language-agnostic as possible, and all the algorithms we will study are illustrated with an implementation in pseudo-code.

Let’s get started!

What is dynamic programming?

Unlike greedy algorithms which produce a global solution by making locally optimal decisions on subproblems (which does not necessarily yield an optimal result), dynamic programming finds an optimal solution by considering all possible possibilities, trying to minimise the number of computations. This is achieved with the help of a cache which stores the result of past computations.

All optimisation problems cannot be solved using dynamic programming: they need to have an optimal substructure. This means that the solution to a problem can be inferred from the solution to the subproblems. An example of problem which does not have optimal substructure is finding the length of the longest simple path on a graph, i.e. the longest path which does not visit the same vertex several times.

Therefore, dynamic programming applies to problems which have optimal substructure and where initial problems are split into overlapping subproblems (otherwise, a simple divide and conquer approach would suffice as there would be no need to store past computations). Dynamic programming algorithms always find an optimal solution.

Dynamic programming relies on two major techniques which we will explore in this article: tabulation and memoisation.

Tabulation and memoisation: introduction and examples

Tabulation, or the bottom-up approach

As the name suggests, an algorithm which uses the bottom-up approach starts by making base computations and then builds the cache up to the target value. For example, say we want to calculate the n-th term of the tribonacci sequence, for some natural number n. The tribonacci sequence is defined by:

Trib(0) = 0; Trib(1) = 1; Trib(2) = 1

Trib(n + 3) = Trib(n) + Trib(n + 1) + Trib(n + 2) for every natural number n.

Here is a naïve solution, which directly implements the definition without optimisations:

Naïve algorithm to recursively calculate the n-th term of the Tribonacci sequence.

The following recurrence tree illustrates the execution of the call tribonacci 6.

We see that most values are computed several times, which makes our code quite slow compared to the number of useful computations. In fact, the function tribonacci has exponential complexity: the runtime complexity is given by T(N) = 3T(N - 1) + Θ(1), so the general term is T(N) = Θ(3^N).

This is where tabulation comes in. Here is a new version of our Tribonacci calculator which uses tabulation:

Dynamic programming algorithm to calculate the N-th term of the tribonacci sequence.

Instead of recursively calculating Trib(N-1), Trib(N-2) and Trib(N-3) to calculate T(N), we simply retrieve them in constant time using the cache array. Therefore, a single recursive call suffices. Since the non-recursive overhead takes constant time, tabulationTribonacci runs in Θ(N) time and takes Θ(N) space.

Memoisation, or the top-down approach

Memoisation and tabulation are very similar as they both take advantage of the same idea of memorising computations to avoid performing them again. The difference is in the order in which values are computed. An algorithm which uses memoisation to calculate the N-th term of the sequence S starts by filling the cache from S(N) down to S(1).

An example where this approach is useful is calculating the binomial coefficient. We define it inductively by the formula Bin(N, K) = Bin(N - 1, K - 1) + Bin(N - 1, K). There are two base cases: for all natural numbers u, Bin(u, 0) = 1 and Bin(u, u) = 1.

Here is an immediate transcription of the above definition:

Naïve algorithm to calculate the binomial coefficient of a pair of numbers.

The loop runs T(n, k) = 2Bin(n, k) - 1 times. Like before, many computations are performed multiple times and storing them would make the the function substantially more efficient.

We could use the bottom-up technique and create an (n*k) two-dimensional array to store the binomial coefficient of all pairs of numbers. A downside of this approach is that it would require to solve more sub-problems than necessary: we would compute Bin(a, b) for a ≤ n and b ≤ k. A solution is to start calculating Bin(n, k) and to recurse down to a base case. This approach is implemented below.

Dynamic programming algorithm to calculate the binomial coefficient of a pair of numbers.

Giving a tight bound for the complexity of this algorithm would be quite complex, but what is sure is that the number of computations cannot asymptotically exceed min( Bin(n, k), (n + 1, k + 1) ), since it cannot be worse than the naïve approach and the number of values is compute is bounded by the size of the cache. For example, calculating Bin(12, 5) takes 71 steps with the dynamic programming approach, as opposed to 1583 steps with the naïve approach.

We’ll learn about another problem where the top-down approach is preferable to the bottom-up approach in the third part, when solving the Knapsack problem.

Now that we have seen the basic techniques used to make a dynamic programming algorithm, we will move on to some concrete problems which we can solve using dynamic programming.

Counting paths in a grid

Let’s start with a simple yet interesting problem.

Problem statement

Let N be a positive integer. We consider an N × N grid. Each square of the grid is represented by a tuple (u, v) corresponding to its coordinates, where u is the horizontal component and v is the vertical component. The top-left corner is at coordinates (0, 0) and the bottom right corner is at (N - 1, N - 1). We can move across the grid, one square at a time, downwards or rightwards: if x(1),…, x(n) is a path then for every index k ≤ n — 1, if x(k) = (u, v) then x(k + 1) is either (u + 1, v) or (u, v + 1).

Illustration of the grid when N = 5.

Our goal is to compute the number of distinct paths from the top-left corner to the bottom-right corner.

Why should we approach this problem using dynamic programming?

First of all, this problem can be solved recursively. We know that there is only one way to reach the top-left corner (0, 0), since it is our starting point: we have found a base case. There are then two ways to reach square (u, v) ≠ (0, 0): either from (u - 1, v) or from (u, v - 1) (we’ll then need to consider pathological cases where u = 0 or v = 0). Therefore, the number of paths to (u, v) is the sum of the number of paths to (u - 1, v) and the number of paths to (u, v - 1).

A naïve solution would take a top-down approach where we start by computing the number of ways to get to (N - 1, N - 1) by computing the number of ways to get to (N - 1, N - 2) and the number of ways to get to (N - 2, N - 1). But both (N - 1, N - 2) and (N - 2, N - 1) are accessible via (N - 2, N - 2), which would therefore be calculated twice: subproblems are overlapping. Therefore, this naïve approach would take non-polynomial time, even if we only have N×N different values to compute.

Writing a solution

We’ll use the recurrence relation we found earlier, we can implement a dynamic programming solution to this problem. The one below uses a two-dimensional array to store the number of distinct paths to every square of the grid.

Dynamic programming algorithm to calculate the number of paths from the top-left corner to the bottom-right corner of an N*N grid.

This algorithm runs in quadratic time (Θ(N²) with respect to the length of the sides of the grid). It goes from the top of the grid to the bottom and from the left to the right so that it does not try to compute the number of paths to square (u, v) before computing both the number of paths to (u - 1, v) and to (u, v - 1) when possible. This is an important thing to notice: when implementing tabulation, you need to make sure that values are computed in the right order, i.e. that you do not try to base a computation on a result which you have not yet calculated.

Pathological cases are handled by the subroutine in lines 13 and 16. When one of the two components (say u) of the coordinates is zero, we set the number of paths coming from (u - 1, v) to 0, since there are no ways we can land in a square from outside the grid.

Lines 23 and 24 manage recursive calls: if the current square is the last of its column, i.e. in the last row (lastRow is true), we move to the next column, starting at row 0. Otherwise, we stay in the same column and increment the row index by one.

For n = 7, we get the following cache:

Number of paths from the top-left corner to all squares of a 7*7 grid.

This shows that there are 924 distinct paths from (0, 0) to (7, 7).

Do it yourself

I encourage you to implement the algorithm we gave in a real programming language. To help you check if your implementation is correct, I have created a repository which contains test cases for some problems. Here is the link:

zak-al/DP-tests

The file paths-in-a-grid.txt has the following format:

n
f n
<blank line>

Where n is the size of the grid (n*n grid) and f n is the number of paths to the bottom-right corner.

The files maximum-path-in-a-grid-positive.txt and maximum-path-in-a-grid-pos-neg.txt contain tests for the first exercise below. They have the following format:

n
l11 l12 ... l1n
.
.
.
ln1 ln2 ... lnn
f n
<blank line>

n is the size of the grid, the n following lines correspond to each row of the grid (with n space-separated integers) and f n is the solution. Integers are between 1 and 45 inclusive in the first file, and between -45 and 45 in the second file.

Exercises

Here are variants and possible improvements of the algorithms we saw:

1. Consider a square grid filled with positive numbers. We define the cost of a path x(1)…x(k) as the sum of the numbers stored in each square in the path. Use an approach similar to the one we took to count paths in a grid, to compute the maximum cost of a path going from the top-left corner to the bottom-right corner. Improve your solution so that it works with arbitrary numbers (positive, negative or zero).
2. Can you improve your solution to the problem above to explicitly compute a path with maximum cost? This should not make the asymptotic bounds for the runtime complexity and the space complexity worse.
   Hint: maintain an additional array which keeps track of whether the maximum path to every square of the grid reached the square from above or from the left. This will enable you to backtrack from the last square to the first square, thus constructing an optimal path.
3. We define the Manhattan distance between (u, v) and (w, x) as |u - w| + |v - x|. Suppose you cannot move to a square (u, v) if its Manhattan distance to the bottom-left corner (at coordinates (0, N)) is less than or equal to N - 2 (where the grid is of size N × N). How many paths are there from the top-left corner to the bottom-right corner? How many elements of the cache array do we need to compute to answer the question?

You can read the second part here:

The art of dynamic programming (pt. 2): classic algorithms

I generated the pseudo-code images using an open source library I wrote in Python. You can find the code there: https://github.com/zak-al/Psi