Dynamic programming: another approach

Both the divide and conquer concepts and dynamic programming seem very similar to one another. Indeed, they both divide problems into smaller more manageable parts, both use recursive techniques to solve problems, and look very similar at first sight. What is the big difference between them? Well, roughly speaking, Dynamic Programming is a kind of Divide and Conquer concept, only it also uses two important methods: memoization and tabulation. These, in turn, create two very important approaches to solving problems with dynamic programming.

Memoization and tabulation – different methods, different problems

Memoization (A Top-Down approach)

Let's try to avoid mentioning Fibonacci numbers and try to solve a less obvious example: the problem of calculating the factorial of a number. Let me remind you, the factorial of the number $5$ (written as $5!$) is $5 \times 4 \times 3 \times 2 \times 1$. That is, by definition: the factorial of the number $n$ is the product of numbers from $1$ to $n$. Important: for mathematical reasons, the factorial of zero is $1$ (that means $0! = 1$). It's logical to assume that we can't avoid reducing to subproblems here either: the factorial of the number $5$ is literally $5 * 4!$.

The intuitive solution to the problem is to reduce it to the calculation of the factorial of the previous number, and so on down to zero – this is the solution by the method of Memoization you are already familiar with. This means that the calculated factorial values are stored for the next queries. Here is the pseudocode, by the way:

// Initialize an array, filled with zeroes. 
// Let's say, 100 – is the maximum value we ever should solve.
// Note: we're using 0-based indexing here.

factorials  = array[0, 100]

for i in [0, 100]:
	factorials[i] = 0

// here goes the factorial function

function factorial(x):
    if x==0:    // if we have a base case
        return 1;
    if factorials[x]!=0:    // if we have already counted it
        return factorials[x]
    return factorials[x] = x * factorial(x-1)    // otherwise, call function and write the answer

// inputting an x – we need to print x!

x = input()
print(factorial(x))

And this program really counts the factorial "Top-Down", meaning that it starts from a large problem and goes to smaller ones. That is why the method of solutions using Memoization is called the Top-Down approach.

Tabulation (A Bottom-Up approach)

What if you do the opposite – start with the smaller ones and go to the larger ones? This technique is called Tabulation, and the solution approach is Bottom-Up. Here is the pseudocode for the same problem (factorials), but using tabulation.

// Initialize an array, 100 – is the maximum value we ever should solve.
// Note: we're using 0-based indexing here.

factorials = array [0, 100]

factorials[0] = 1;    // base case

// and now we iteratively fill this array

for i in [1, 100]:
    factorials[i] = factorials[i-1] * i;    // use the definition of the factorial

// inputting an x – we need to print x!

x = input()
print(factorials[x])

You can see the difference straight away, right? We don't call the function recursively, we just fill in all the array values that we might theoretically need. And then we just use the resulting array for whatever queries we need.

It sounds simpler, but let's analyze at once the fundamental differences between the two approaches and when to use which. It is immediately apparent that tabulation does not require recursion, but only a recurrence formula, by which one subproblem depends on another (by the way, there is not always such a simple formula). On the other hand, Memoization solves only those subproblems that were needed for the original problem; unlike tabulation, which must go through all possible subproblems. At the same time, some of its solutions may remain unused until the end of the program, taking up space and work time.

By the way, didn't you notice anything strange about Memoization here? Yes, here it wasn't so useful, because in this problem there are no overlapping subproblems within a single problem. Sometimes it really happens, and the Tabulated array helps us to respond to several queries very fast, but Memoization is not as useful as Fibonacci's problem (oops, we mentioned it, but it was worth pointing it out this time).

1D and 2D dynamic programming

1D Dynamic Programming

Let's try to solve a simple and well-known dynamic programming problem. Suppose we have a ladder, and on the top step lies a ball. It can jump down to the next step, over one step, and over two steps (arrows on the picture below). How many ways can the ball go down if there are a total of $n$ steps?

The solution is based on the addition of ways: if the ball can get to the $i$ step in $x$ ways, to the $i+1$ step in $y$ ways, and to the $i+2$ step in $z$ ways, then it will have $x+y+z$ ways to get to the $i+3$ step. In the picture, there are a number of ways to each step written under those steps. How do we make this into a solution for $n$ steps?

If we use memoization, we have to recursively call the function for the subproblems (for the 3 previous steps). That's the top-down solution:

// inputting the number of steps

n = input()

// initialize an array sized n, fill it with zeroes
ways = array[1, n]   

for i in [1, n]:
    ways[i] = 0

function count_ways(n):
    if n == 3:
        return 2
    if n < 3:
        return 1
    if ways[n] != 0:
        return ways[n]
    return count_ways(n-1) + count_ways(n-2) + count_ways(n-3)
 
print(count_ways(n))

And if we use tabulation, we make an array and fill it iteratively. In both cases, you'll have to manually fill in the base cases. Here is the bottom-up solution:

// inputting the number of steps

n = input()

ways = array[1, n]   
ways[1] = 1    // base cases
ways[2] = 1
ways[3] = 2
 
for i in [4, n]:
    ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3] // use our addition of ways rule
 
print(ways[n])

This was a good example of a one-dimensional dynamic programming problem. It is one-dimensional because we have a one-dimensional array (and because the ball moves in one dimension, of course).

But what would happen if we tried both of these approaches on a two-dimensional problem? For example, this one.

2D Dynamic Programming

Imagine a cellular matrix (for simplicity, let it be square, of size $n*n$). Each cell has a cost to get into that cell. You are standing in the upper left corner, you need to get to the lower right corner with the minimum total cost of the path. You can only go to the right and down (this makes sense if you want to minimize the cost). Here's what it looks like:

The question is: What is the minimum cost of such a path?

Let's try to imagine what the subproblem would be here. For example, we know the minimum cost to get to the cell at the top and the cell to the left. What then is the minimum cost to get to our final cell? Obviously, the minimum of these two plus the cost of that particular cell.

Then let's create a two-dimensional array of size $n*n$, too, and write in cell $[i][j]$ the minimum cost of the path to the cell $[i][j]$ in the original matrix. It is clear that for the upper row, the rule will turn into the sum of the costs of the path to the cell on the left and the cost of the cell itself. Similarly for the first column:

And then we will apply this formula to all table cells: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j], where arr is the array where the original matrix is stored, and dp is our array of cost sums (dp from Dynamic Programming – that is usually the name of such arrays). In fact, this is what the solution will be:

dp = array[1,n][1,n] 

// now calculate each cell
for i in [1, n]:
    for j in [1, n]:
        if (i == 1 && j == 1):
            // top-left cell
            dp[i][j] = arr[i][j];
        else if (i == 1):
            // topmost row
            dp[i][j] = dp[i][j - 1] + arr[i][j];
        else if (j == 1):
            // leftmost column
            dp[i][j] = dp[i - 1][j] + arr[i][j];
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j]

// finally, the answer is in the bottom-right cell
print(dp[n][n])

And the final dp array will look like this:

So, the answer is 28 – the minimum cost of the path.

As you noticed, the two-dimensional problem here is solved only with tabulation. You may have already guessed the reason: for each cell, you would have to make two recursive calls, i.e. roughly $2n^2$ calls. This is quite a heavy load, and there are also problems where we have to look at the element on the diagonal, for example, which would be even worse for our program.

Conclusion

Looking at the main takeaways from dynamic programming:

• Two methods can be distinguished: tabulation and memoization; they form two approaches: bottom-up and top-down.

• If there is a strict recurrence formula and it is possible to count "extra" data, it is mostly more convenient to use the bottom-up approach.

• If there is no exact relationship between subproblems, but there is definitely an intersection of subproblems somewhere, then it is worth trying top-down.

• These two approaches make dynamic programming a separate solution method within the "Divide and Conquer" concept.