Visualizing Dynamic Programming as Tables

Dynamic programming is all about storing results in a table to recall them later. So it makes sense that we can use a table to visualize this process. A table can show us where the computed values come from and how they are combined to form optimal solutions. Just like with the other visualizations though, a table will provide better insights to some problems than others. For example, a table can show us how the Fibonacci numbers are computed but so does a recursion tree. The former does not provide any more information than the latter can for this problem. Which is why it is important to have multiple ways of viewing our problems. Previously we explored how dynamic programming can be represented by directed acyclic graphs and the insights such graphs can give us. Directed acyclic graphs helped us see how the solutions of subproblems can be used to construct the overall solution. Tables can provide with similar insights but in a way that can be directly applied in code. After all, dynamic programming is all about using tables.

Get Computing Macroxela’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Let’s look at a particular problem and see how visualizing tables can help us solve it: longest common subsequence. The longest common subsequence problem is exactly what its name describes, it finds the longest subsequence common between two sequences. The subsequence may or may not be composed of consecutive characters. For example, the longest common subsequence between apple and planet is ple. The characters are consecutive in the first sequence but not in the second sequence. However, the order remains the same. Let’s start by creating an empty table to represent the one our dynamic programming algorithm will use to solve the problem. We will use the words planet and apple as our example.

The table contains an extra row and column to make computations easier. These will be filled with 0s as the base cases for the problem. For this example, we will use a bottom-up approach to build our solution (top-down can also be used but it is usually easier to visualize tables with a bottom-up approach). We will also compare the first letter of planet with every letter in apple, then the second letter of planet with every letter in apple and so on, filling out the table row by row. The longest common subsequence is composed of smaller common subsequences so we can use the smaller subsequences to build our solution. But which smaller subsequences? And how do we combine them? We need to think of the base cases to help us with this. The base case is an empty sequence, which gives us a value of 0 hence all of the 0s in the extra row and column. The next easiest case would be a single character in each sequence. If they match, the subsequence is of length 1. This is just 1 plus the result of the base case. If they do not match, it should be 0 which is just the result of the base case. So comparing the first letters of each word, we see that they do not match hence the result is simply the result of one of the base cases. However, we have more than one base case so which one do we pick? Since we are looking for the longest common subsequence, we need the largest value so we take the max between the previous cases. For now, this does not make much of a difference but we will see that difference later on. We can see the table after this first check below.

In the next subproblem we compare p to ap, a single character to a word with two characters. We have a matching character in this case, both have a p so we need to adjust the value accordingly. As stated before, this is just 1 plus the value of the previous case. This turns out to be the one to the top-left of the current cell. We can observe this change in the following table.

Why don’t we add 1 to the cases directly above or to the left of the current cell? It doesn’t seem to make a difference right now but let’s take another iteration. On the next iteration, we compare p to app. Once again, we have a matching character so we should increase the value of one of the previous cases by 1. However, if we use the value to the left of the current cell, we would get 2. And that’s wrong. The longest subsequence between p and app is p which is of length 1 not 2. So we cannot use the case to the left of the current cell. The same logic applies to the cell directly above, which we can see if we simply switch the places of apple and planet on the table. Hence we need to use the cell to the diagonal-top-left of the current cell. This makes more sense when we consider what this cell actually represents. Each cell and row represents a particular sequence up to a certain character. In our current case, the cell represents the comparison between p and app. This is the comparison of both sequences up to and including the current letter. The cell to the diagonal top-left represents the comparison of both sequences excluding the current character. Which makes sense to use when the current character matches. If the current character matches, we do not want to count it twice, which would happen if we pick the cell above (representing removing the matching character from one sequence and not the other) or to the left (representing removing the matching character from the other sequence instead). We can see this in the following table.

The remainder of the row is populated with 1s since no other characters match and the maximum between the top case and left case is stored in each cell, which is always 1 after the first one. We see something similar happen in the following row for character l. Once again, the cells are populated with the largest value, 1, until we find a matching character. When comparing the l from pl with the l from appl, we get another match. Thus we increase the value by one again, giving us a result of 2.

By now we should be getting a grasp of how the problem works. Whenever the characters match, we take the result of the subsequence without the current character and add 1 to it. When they don’t match, we take the maximum between the results when the current character is removed from one or the other sequence. We can fill out the table according to these rules as shown below. The last position stores the result for our problem, which is 3 in this case.

Can we turn our observations into actual code? Using the table and what we discovered from it, we should be able to do so. We first need a table which can be done with the following code. The table needs an extra row and column hence the +1 on the m and n values representing the lengths of the sequences.

n, m = len(s1), len(s2)
table = [[0 for i in range(m+1)] for j in range(n+1)]

To iterate through the table we need some nested loops. We can do this using for loops iterating from 1 to the length of the sequence plus 1 (remember the extra row & column).

for i in range(1, n+1):
  for j in range(1, m+1):

We now convert the rules we previously developed into code. One of the rules was to increase the value of the diagonal top-left cell by one whenever the characters match. This can be done with a single if statement and another line to set the value of the current cell in the table. Because we have an extra row and column at the beginning of the table, we compare the i-1 and j-1 characters in the sequence and use the same indices to access the previous cells.

if s1[i-1] == s2[j-1]:
  table[i][j] = table[i-1][j-1] + 1

The other rule was to store the max between the top cell and the left cell when the characters do not match. This requires using a max function and accessing the previous cells by using i-1 and j for the top cell and i and j-1 for the left cell.

else:
  table[i][j] = max(table[i-1][j], table[i][j-1])

Combining all of the previous code results in the following code.

def LCS(s1, s2):
  n, m = len(s1), len(s2)
  table = [[0 for i in range(m+1)] for j in range(n+1)] 
    
  for i in range(1, n+1):
    for j in range(1, m+1):
      if s1[i-1] == s2[j-1]:
        table[i][j] = table[i-1][j-1] + 1
      else:
        table[i][j] = max(table[i-1][j], table[i][j-1])
  return table[n][m]

So what did the table show us? It did not demonstrate how the problems overlap which is crucial for dynamic programming to be used effectively. But it did show us how the optimal solutions combine to form greater optimal solutions. And it demonstrated the connection between the subproblems. It allowed us to find the pattern between the subproblems and generalize it to an actual algorithm. The table revealed what the optimal substructure of the problem is which gave us the insight to develop the algorithm and implement it in code. Now the next time we see a problem amenable to dynamic programming, we can use a table to visualize the process and figure out how to implement it.