Debugging lab: DP bugs in Python

Why this matters

A dynamic programming (DP) program can run without any error and still print the wrong answer. No exception is thrown, no line is marked red, and the output looks like a number. The only way to notice is to check the answer against something you know. This lesson gives you a method for that, and then several broken programs to practise it on.

The bugs in this lesson are the ones that appear most often when people write DP for the first time:

• a wrong base case, which is the answer for the smallest input, written into the table by hand
• a bad fill order, which means a cell is read before the program has written it
• zero used as a sentinel, which means zero is the value for "no answer yet" and then zero wins a comparison it should lose
• a negative index, which Python accepts without complaint and which then reads the wrong cell

Each bug below comes with a program that runs, its real output, a diagnosis and a fix. The earlier lessons in this module showed how to build these tables. This lesson assumes you know the basic loop from them, and it does not repeat the derivations.

Words you need first

A table is a list that stores the answer to every smaller question. In Python a two-dimensional table is a list of lists, written dp[i][j]. The cell dp[i][j] is one answer.

A base case is an answer that you write in directly, without computing it from other cells. For coin change it is the number of ways to make amount 0. For a grid it is the first cell.

A fill order is the order in which the loops write cells. A cell can use only cells that were already written. If a cell reads another cell that is still empty, the result is wrong, and Python gives no warning.

A default value is the value a cell holds before you write to it. Python has no default for a list slot. A cell keeps the value the list was created with. For [0] * n, that value is 0, so a cell that you never wrote still holds 0, and a program can read it as if it were a real answer.

A sentinel is a special value that means "no answer here", for example "this cell is unreachable". A sentinel is safe only when no real answer can equal it. Zero is often a real answer, for example a cost of zero or an empty run. So zero is a bad sentinel for a minimum or a maximum. In Python two common sentinels are None, which means "no value", and float("inf"), which is infinity, a number larger than any real cost.

A negative index counts from the end of a list. dp[-1] is the last cell and dp[-2] is the one before it. Python allows this, so a loop that reads dp[i - 1] when i is 0 does not raise an error. It reads the last cell.

The debugging method

Use the same five steps for every bug in this lesson.

1. Choose a tiny input that you can solve on paper, for example a 3 by 3 grid or an amount of 5. Work out the right answer before you run anything.
2. Run the program and compare its output with your answer. If they match, try one more input before you stop.
3. Print the whole table. Scan it in the order the loops fill it. The first wrong cell is the one that matters. Later wrong cells usually come from it.
4. Read the lines that write that first wrong cell. Ask three questions. What did it read? Was that value already final? Was the base case written?
5. Change one thing, then run the same tiny input again. A fix that changes a second line at the same time makes it hard to know which change helped.

The labs below follow this order.

Lab 1: a wrong base case in coin change

The problem is to count the ways to make an amount from a set of coins, where the order of the coins does not matter. With coins 1, 2 and 5, the amount 5 can be made in 4 ways: one coin of 5, two coins of 2 and one coin of 1, one coin of 2 and three coins of 1, and five coins of 1.

The list ways has one cell for each amount from 0 to 5. The cell ways[a] counts the ways to make the amount a. Each coin is used in turn, and ways[a] gains the count ways[a - coin] for each amount a that is at least the coin.

Step 1 is the tiny input. Amount 0 has one way to make it: use no coins at all. So the table should print 1 for amount 0. Amount 5 should print 4.

Here is the program. It has a bug in the base case.

The output is:

ways to make 5: 0
ways to make 0: 0

Step 2 shows the mismatch. The program prints 0 for amount 5, and we expected 4.

Step 3 asks where the table first goes wrong. Cell 0 is the first cell in the table, and it holds 0. We expected 1 there. Every other cell is built by adding earlier cells. Starting from 0, each addition adds 0, so every cell stays 0.

Step 4 reads the line that writes cell 0. The line is ways[0] = 0. This line is the base case, and it is wrong. The number of ways to make amount 0 is 1, not 0, because the empty set of coins is a valid way.

Step 5 changes that one line and runs the same program again.

ways[0] = 1

The output is now:

ways to make 5: 4
ways to make 0: 1

The base case is the only change. The loops did not need to change.

Lab 1b: the first row and column of a grid

The same kind of bug appears in grids. The question is the cheapest route from the top-left cell to the bottom-right cell, moving only right or down, where each cell has a cost. The table dp[i][j] holds the cheapest cost to reach cell (i, j).

The grid is:

1 3 1
1 5 1
4 2 1

The cheapest route is down the first column, then right along the bottom row, with cost 1 + 1 + 4 + 2 + 1 = 9. A cheaper route is right along the top row and then down the last column: 1 + 3 + 1 + 1 + 1 = 7. So the answer is 7.

The program below fills the table from cell (1, 1) onward, and it forgets to fill the top row and the left column.

The output is:

[1, 0, 0]
[0, 5, 1]
[0, 2, 2]
minimum path sum: 2

The expected answer is 7, and the program prints 2, which is smaller than any real route can cost. The table in the output shows why.

The first row and the first column hold 0 after the start. Those cells were never written, so they still hold the 0 that the list was created with. When cell (2, 1) takes the minimum of its two neighbours, the cell to its left, (2, 0), still holds 0 and the minimum picks it. The 0 is not a cost. It is a cell that was never computed.

The fix is to write the base row and column before the main loops. Each cell in the first row can be reached only from the left, and each cell in the first column only from above.

for j in range(1, cols):
    dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, rows):
    dp[i][0] = dp[i - 1][0] + grid[i][0]

With these two loops added before the main loop, the output is:

[1, 4, 5]
[2, 7, 6]
[6, 8, 7]
minimum path sum: 7

Lab 2: a bad fill order in a 0/1 knapsack

A knapsack problem asks which items to put into a bag with a weight limit so that the total value is as large as possible. In the 0/1 version each item can be taken at most once. A common way to save memory is a single list best, where best[c] is the best value that fits in capacity c. The list is updated once for each item.

The loop over capacity must run in one direction. Here is a program that runs the loop the wrong way. The only item is weight 2 and value 3, and the capacity is 5. zip(weights, values) pairs the two lists, so w, v takes the weight and the value of each item in turn.

The output is:

best value with capacity 5: 6

There is only one item, so the right answer is 3. The program says 6, which is two copies of the item. Its total weight is 4, which fits in 5, so the program has used the same item twice.

Step 3 says to trace the table in the order it is written. The loop goes up, so when it reaches capacity 4 it reads best[2]. That value was written a moment earlier in the same loop, by the same item. The loop has used the item once to fill best[2] and then reads that value as if the item were still unused.

• At c = 2: best[2] becomes best[0] + 3 = 3.
• At c = 3: best[3] becomes best[1] + 3 = 3.
• At c = 4: best[4] becomes best[2] + 3 = 3 + 3 = 6. This is the second use of the item.
• At c = 5: best[5] becomes best[3] + 3 = 6.

The fix is to run the capacity loop from the top down to the item's weight. range(capacity, w - 1, -1) counts down from capacity to w, because the end number is not included and w - 1 stops the loop at w. Then best[c - w] is still the value from before this item was considered, because every cell it depends on has a smaller index and is written later.

for c in range(capacity, w - 1, -1):
    best[c] = max(best[c], best[c - w] + v)

The output is now:

best value with capacity 5: 3

Lab 2b: a cell that needs a later cell

A grid can have the same problem in two dimensions. Suppose cost[i][j] is the cheapest cost from cell (i, j) to the bottom-right cell, moving right or down. Then each cell depends on the cell below it and the cell to its right. Those cells must be filled first, so the loops must start from the bottom-right corner.

The program below uses the same grid as Lab 1b, but it fills the table from the top-left corner.

The output is:

cheapest route from top-left: 1

The expected answer is 7. The first cell, cost[0][0], reads cost[1][0] and cost[0][1]. Both are below or to the right of it, and the loops have not reached them yet. They still hold 0, so the minimum picks 0 and the cell gets only its own cost, 1.

The fix is to reverse both loops, so that the bottom-right corner is filled first and every cell is written after the cells it reads.

for i in range(n - 1, -1, -1):
    for j in range(n - 1, -1, -1):

The rest of the code stays the same. The output is now:

cheapest route from top-left: 7

Lab 3: zero used as a sentinel

A sentinel marks a cell as "no answer". The trouble starts when the sentinel is zero, because zero can also be a real answer. A minimum over cells that include a zero sentinel picks the zero, and a maximum over cells with a zero sentinel can pick a zero that means "nothing".

Lab 3a: unreachable cells in a minimum

This grid has a wall of blocked cells in the middle column, which means no route can cross to the right side. The question is the cheapest cost to reach the bottom-right cell from the top-left one. The correct answer is -1, meaning no route exists. The program below treats each blocked cell as a cell that was never written, and that cell holds 0.

The output is:

cheapest cost to bottom-right: 1

The expected output is -1. The program prints 1, which is the cost of a single cell, as if there were a route that cost nothing to reach. Trace the walls. The cell (0, 2) is reached only from the wall at (0, 1), so its value is 3 + 0 = 3. The cell (1, 2) takes the minimum of (0, 2) and the wall (1, 1), which is 0, so its value is 1 + 0 = 1. The bottom-right cell then takes the minimum of (1, 2) and the wall (2, 1), again 0, and gets the value 1.

The walls and unreached cells all hold 0, and 0 is less than every real cost. So the minimum always picks a wall.

The fix uses a sentinel that no real answer can equal. Here it is INF = float("inf"), which is larger than every real cost. Every cell starts at that value. A cell is computed only when at least one neighbour is reachable, and the final answer is -1 if the target still holds the sentinel. The changed program is:

The output is:

cheapest cost to bottom-right: -1

A sentinel must not be a value a real answer can take. float("inf") works here because every real cost is far below it. In Python, adding a cost to infinity still gives infinity, so the addition does not break anything. The check if best != INF is still the clearest way to say that no neighbour was reached, and it stops the program from adding a cost to a value that was never computed.

Lab 3b: a zero start in a maximum

The next bug uses the same idea in a different problem. The question is the largest sum of a run of numbers, where a run is a list of numbers next to each other and must contain at least one number. This is the maximum subarray problem. The program below starts its best answer at 0.

The output is:

largest sum of a run: 0

The expected answer is -1, which is the largest single number. A run has to contain at least one number, so an empty run that sums to 0 is not allowed. But best starts at 0, which is the empty run. When every number is negative, the empty run wins, and the program prints 0.

The fix is to start both values from the first number, so that best can only be a run that contains at least one number. The loop then covers the rest of the list, nums[1:]. The first number is already in both values, and visiting it again would add it to itself. For [5, 1], a loop over every number, with both values starting at the first number, gives 11, but the correct answer is 6, and the loop over nums[1:] gives 6.

current = nums[0]
best = nums[0]
for x in nums[1:]:
    current = max(x, current + x)
    best = max(best, current)

The output is now:

largest sum of a run: -1

Starting both values at float("-inf") also gives the right answer in Python. Adding a negative number to negative infinity still gives negative infinity, and Python integers never wrap around. Starting from the first number is still the clearer choice, because the code then says what the first value is.

Common mistakes

Array sized one too small. A table for amounts 0 to 5 needs six cells. If you create a list of size amount, the last cell does not exist. The program below does this.

The output is:

Traceback (most recent call last):
  File "...", line 7, in <module>
    ways[a] += ways[a - coin]
    ~~~~^^^
IndexError: list index out of range

The file name depends on where the file is saved. The last line is the exact message. The loop writes ways[5], but the list has indexes 0 to 4. The message does not name the bad index or the list length, so read the line that the traceback points to. The fix is [0] * (amount + 1), the same size as the table in Lab 1.

Reading before the first cell. A loop that starts at 0 and reads dp[i - 1] reads index -1 on its first pass. dp[-1] is the last cell, so nothing is raised. The program below does this, and it prints the table so you can see the result.

The output is:

[0, 0, 0, 0, 0]
0

The program finishes, and the answer is 0 where 16 was expected. Each dp[i - 1] on the first pass reads dp[-1], which is the last cell, and that cell is 0. The 1 written to dp[0] is then overwritten with 0, and every later cell copies that 0. The fix is to start the loop at 1, since cell 0 is the base case that was already written.

for i in range(1, n):
    dp[i] = dp[i - 1] * 2

With that change the output is:

[1, 2, 4, 8, 16]
16

When a DP program gives a result that is too small or always 0, check the loop start and the base case first.

The same list in every row. This mistake is specific to Python. [[0] * 3] * 3 makes a list that holds the same inner list three times, not three separate lists. Changing one cell then changes that cell in every row. The program below shows it, and the line after it shows the fix.

The output is:

[[5, 0, 0], [5, 0, 0], [5, 0, 0]]
[[5, 0, 0], [0, 0, 0], [0, 0, 0]]

[0] * 3 makes one new list of three zeros. Repeating it with * 3 puts the same list object into all three slots. The list comprehension [[0] * 3 for _ in range(3)] makes a new inner list on each pass, so each row is separate. Use the comprehension for every two-dimensional table.

Changing the base case to fix a symptom. A program that prints 0 for every input often has a base case of 0 that should be 1, as in Lab 1. A program that prints a number that is too small often has a default 0 in a cell the loops never write, as in Lab 1b. Find the first wrong cell before you change a line.

Testing only one input. The bugs in this lesson can give correct answers on some inputs. A single item with weight 5 and capacity 5 would not show the forward-loop bug. The input in Lab 2 does. A test should include a case where the answer is known and where a repeated item or an empty choice would change the result.

Practice

Exercise 1. The program below counts the ways to climb a staircase of 4 steps, taking 1 or 2 steps at a time. It prints 3. The correct answer is 5. Find the bug.

ways = [0] * 5
ways[0] = 0
ways[1] = 1
for i in range(2, 5):
    ways[i] = ways[i - 1] + ways[i - 2]
print(ways[4])

Show the answer

The base case ways[0] is 0, but it should be 1. Zero steps is one way to stand at the bottom, so every later cell is too small. Changing the line to ways[0] = 1 makes the program print 5. A run of this program with the change prints 5, which matches the list of five ways: 1111, 112, 121, 211 and 22.

Exercise 2. The program below computes the cheapest cost to finish a path of n cells, where from cell i you may jump one or two cells ahead, and jumping past the end costs nothing. It has dp sized n + 2, and the cells dp[n] and dp[n + 1] are 0. The loop is:

for i in range(n):
    dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])

Explain the bug and give the fix.

Show the answer

Cell dp[i] reads dp[i + 1] and dp[i + 2], which are later cells. The loop goes up, so those cells are still 0 when dp[i] is computed. The fix is to run the loop from the end to the start: for i in range(n - 1, -1, -1):. Then both later cells are final when they are read. With the cost list [1, 2, 3, 4], the upward loop gives 1 and the downward loop gives 4.

Exercise 3. The maximum-run program in Lab 3b, with best and current both starting at 0, is run on the list [-5, -2]. What does it print, what should it print, and what is one correct fix?

Show the answer

It prints 0. It should print -2, which is the largest single number, because a run must contain at least one number. One correct fix is to start current and best from nums[0] and loop over nums[1:]. Starting both from float("-inf") is also correct in Python.

Exercise 4. Choose the smallest input for coin change that would show a wrong base case of 0 in ways[0]. Give the input and the expected output.

Show the answer

Coins [1] and amount 0 is one small choice. The expected output is 1, because the empty set of coins is the only way. With a base case of 0 the program prints 0 and the bug is visible. A second choice is coins [1, 2] and amount 2, where the answer is 2 (the coins 2, or 1 and 1). This one also needs the loop to be right, so it is the better test.

Exercise 5. The program below is coin change with the amount loop reversed, so that it runs from amount down to the coin. It is run on coins [1, 2] and amount 2. The expected output is 2. What does it print, and why?

ways = [0] * 3
ways[0] = 1
for coin in [1, 2]:
    for a in range(2, coin - 1, -1):
        ways[a] += ways[a - coin]
print(ways[2])

Show the answer

It prints 1. With the loop running down, each coin is used at most once, the same pattern as the 0/1 knapsack in Lab 2. The coin 1 pass visits cell 2 before cell 1, so cell 2 reads ways[1] while it is still 0 and adds nothing. Cell 1 becomes 1 after cell 2 has already been passed. Then the coin 2 pass adds ways[0], which is 1, so ways[2] ends at 1. That is the single way of using the coin 2 alone. The second way, two coins of 1, is lost. The fix is to make the amount loop run upward, as in Lab 1.

Summary

• A DP program can run without error and still give a wrong answer, so check a tiny input by hand against the output.
• Print the table and find the first wrong cell in fill order. The lines that write that cell usually explain the bug.
• A base case must hold the true answer for the smallest input, and a cell that the loops never write still holds the value the list was created with, here 0.
• A negative index does not raise an error in Python, so check that a loop never reads dp[i - 1] before dp[0] has been written.
• A cell must be written before any cell that reads it, which means the loop direction matters in 1D knapsack and in grids that depend on cells below or to the right.
• Use a sentinel that no real answer can equal, such as None or float("inf"), and check for it before using the value.
• Build two-dimensional tables with a list comprehension, so that each row is a separate list.