Debugging lab: DP bugs

Why this matters

Most dynamic programming bugs do not crash. The program compiles, runs, and prints a number, and the number is wrong. A test that uses a large input will not show you which part broke. You need a small input, a table of stored values, and a hand trace that you can check line by line.

This lab gives three buggy programs. Each one has a single kind of mistake that comes up often in DP code:

• a wrong base case, which is the value stored for the smallest input
• a bad fill order, which computes a cell before the cells it depends on
• zero used as a sentinel, which is a special value that means "not set", where zero is also a real answer

Every program is short. You will trace each bug on paper first, then run the program and compare its output with your trace.

The earlier lessons in this module built the methods: memoization, tabulation, and rolling rows. This lesson assumes you know them and only looks at how they go wrong. The longest path lesson before this one covers topological order, which is a fill order for graphs.

A checklist for DP bugs

Use these four checks in order. Most bugs are caught by one of them.

1. Base cases. Write down the stored value for the smallest inputs, such as 0 steps or the first cell. Ask whether the value matches the meaning of the table. A base case says how many ways there are to do nothing, or what the cost is at the start.
2. Fill order. For each cell, list the cells it reads. Every one of them must be computed before the current cell. If you iterate in the wrong direction, a cell may read an old value.
3. Sentinels. A sentinel is a special value that means "not set" or "unreachable". Find every place where the program reads a table value. Ask whether a real answer can equal the sentinel.
4. Small input table. Run the program on the smallest input that exercises the logic. Print the table after each step. Compare it cell by cell with your hand trace.

When you debug, use .at() instead of [] for vector access. .at() checks the index and throws an exception if it is out of range. [] does not check, so a bad index can silently read garbage. The checks cost a little speed, so remove them once the bug is fixed if speed matters.

The lab file

The file below contains the three buggy programs, the fixed version of each, a trace helper for the grid program, and a main function that runs all of them on small inputs. It is one file, so you can compile and run it in one step.

#include <iostream>
#include <vector>
 
// Program 1: ways to climb n steps, taking 1 or 2 steps at a time.
long long climb_buggy(int n) {
    std::vector<long long> ways(n + 1, 0);
    ways[0] = 0;  // BUG: zero steps is one way (take no steps).
    if (n >= 1) {
        ways[1] = 1;
    }
    for (int i = 2; i <= n; ++i) {
        ways[i] = ways[i - 1] + ways[i - 2];
    }
    return ways[n];
}
 
long long climb_fixed(int n) {
    std::vector<long long> ways(n + 1, 0);
    ways[0] = 1;
    if (n >= 1) {
        ways[1] = 1;
    }
    for (int i = 2; i <= n; ++i) {
        ways[i] = ways[i - 1] + ways[i - 2];
    }
    return ways[n];
}
 
// Program 2: paths in a grid that moves right or down, using one row of counts.
long long grid_paths_buggy(int rows, int cols) {
    std::vector<long long> row(cols, 1);
    for (int r = 1; r < rows; ++r) {
        for (int c = cols - 1; c >= 1; --c) {  // BUG: fills right to left.
            row[c] += row[c - 1];
        }
    }
    return row[cols - 1];
}
 
long long grid_paths_fixed(int rows, int cols) {
    std::vector<long long> row(cols, 1);
    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            row[c] += row[c - 1];
        }
    }
    return row[cols - 1];
}
 
void grid_trace(int rows, int cols, bool right_to_left) {
    std::vector<long long> row(cols, 1);
    std::cout << "  row 0: ";
    for (long long x : row) std::cout << x << ' ';
    std::cout << "\n";
    for (int r = 1; r < rows; ++r) {
        if (right_to_left) {
            for (int c = cols - 1; c >= 1; --c) row[c] += row[c - 1];
        } else {
            for (int c = 1; c < cols; ++c) row[c] += row[c - 1];
        }
        std::cout << "  row " << r << ": ";
        for (long long x : row) std::cout << x << ' ';
        std::cout << "\n";
    }
}
 
// Program 3: fewest jumps to reach the last index. nums[i] is the longest jump from i.
int min_jumps_buggy(const std::vector<int>& nums) {
    const int n = static_cast<int>(nums.size());
    std::vector<int> dp(n, 0);  // BUG: 0 means "not reached", but 0 is also a real answer.
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (j + nums[j] >= i) {
                const int candidate = dp[j] + 1;  // BUG: dp[j] may be "not reached".
                if (dp[i] == 0 || candidate < dp[i]) {
                    dp[i] = candidate;
                }
            }
        }
    }
    return dp[n - 1];
}
 
int min_jumps_fixed(const std::vector<int>& nums) {
    if (nums.empty()) {
        return -1;
    }
    const int n = static_cast<int>(nums.size());
    std::vector<int> dp(n, -1);  // -1 means "not reached".
    dp[0] = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] == -1 || j + nums[j] < i) {
                continue;
            }
            const int candidate = dp[j] + 1;
            if (dp[i] == -1 || candidate < dp[i]) {
                dp[i] = candidate;
            }
        }
    }
    return dp[n - 1];
}
 
int main() {
    std::cout << "Program 1: climb steps\n";
    for (int n = 0; n <= 4; ++n) {
        std::cout << "  n=" << n << " buggy=" << climb_buggy(n)
                  << " fixed=" << climb_fixed(n) << "\n";
    }
 
    std::cout << "\nProgram 2: grid paths\n";
    std::cout << "  3x3 fill left to right (fixed):\n";
    grid_trace(3, 3, false);
    std::cout << "  3x3 fill right to left (buggy):\n";
    grid_trace(3, 3, true);
    std::cout << "  2x2 buggy=" << grid_paths_buggy(2, 2) << " fixed=" << grid_paths_fixed(2, 2) << "\n";
    std::cout << "  3x3 buggy=" << grid_paths_buggy(3, 3) << " fixed=" << grid_paths_fixed(3, 3) << "\n";
    std::cout << "  3x4 buggy=" << grid_paths_buggy(3, 4) << " fixed=" << grid_paths_fixed(3, 4) << "\n";
 
    std::cout << "\nProgram 3: minimum jumps\n";
    const std::vector<std::vector<int>> tests = {
        {2, 3, 1, 1, 4},
        {1, 0, 2},
        {1, 0, 5, 1, 1},
    };
    for (const auto& nums : tests) {
        std::cout << "  nums=";
        for (int x : nums) std::cout << x << ' ';
        std::cout << " buggy=" << min_jumps_buggy(nums)
                  << " fixed=" << min_jumps_fixed(nums) << "\n";
    }
    return 0;
}

Compile and run it with:

g++ -std=c++20 -Wall -o lab32 lab32.cpp
./lab32

The compiler printed no warnings. The program printed this (g++ 15.2.0 on Linux):

Program 1: climb steps
  n=0 buggy=0 fixed=1
  n=1 buggy=1 fixed=1
  n=2 buggy=1 fixed=2
  n=3 buggy=2 fixed=3
  n=4 buggy=3 fixed=5
 
Program 2: grid paths
  3x3 fill left to right (fixed):
  row 0: 1 1 1 
  row 1: 1 2 3 
  row 2: 1 3 6 
  3x3 fill right to left (buggy):
  row 0: 1 1 1 
  row 1: 1 2 2 
  row 2: 1 3 4 
  2x2 buggy=2 fixed=2
  3x3 buggy=4 fixed=6
  3x4 buggy=4 fixed=10
 
Program 3: minimum jumps
  nums=2 3 1 1 4  buggy=2 fixed=2
  nums=1 0 2  buggy=0 fixed=-1
  nums=1 0 5 1 1  buggy=1 fixed=-1

The rows of the grid trace end with a space, because the helper prints a space after each number.

Bug 1: a wrong base case

The first program counts the ways to climb a staircase of n steps, taking one step or two steps at a time. Let ways[k] be the number of ways to climb k steps. The rule is ways[k] = ways[k - 1] + ways[k - 2]: the last move was either a one-step move from k - 1, or a two-step move from k - 2.

The rule needs starting values, which are the base cases. For one step there is one way. For zero steps there must also be a value. The meaning of zero steps is "take no steps", and there is exactly one way to do that. So ways[0] should be 1.

The buggy version sets ways[0] = 0. Trace n = 2 by hand:

• ways[1] = 1, correct.
• ways[2] = ways[1] + ways[0] = 1 + 0 = 1. The correct answer is 2: one step then one step, or two steps at once.

The output shows the same mistake for every n from 2 up. The answer for n = 1 is right because it only uses ways[1], which is set directly. Each buggy answer is the correct answer for one step fewer, which is why n = 4 gives 3 instead of 5.

Look at the pattern in the output. The answers are wrong, but they look plausible. A bug that gives plausible numbers is the hardest kind to find, which is why the checklist starts with base cases.

The fix is one line: ways[0] = 1.

A related bug: a loop that starts too early

A missing or misplaced base case can also make the program read a position that is not in the table. The next program uses a loop that starts at i = 1 instead of i = 2. On the first pass it reads ways.at(i - 2), which is ways.at(-1).

#include <iostream>
#include <vector>
 
int main() {
    int n = 3;
    std::vector<long long> ways(n + 1, 0);
    ways[0] = 1;
    ways[1] = 1;
    for (int i = 1; i <= n; ++i) {  // starts one step too early
        ways.at(i) = ways.at(i - 1) + ways.at(i - 2);
    }
    std::cout << ways.at(n) << "\n";
    return 0;
}

Compile and run it. The program stops with this output, which is the real message from g++ 15.2.0 and the C++ library on this machine:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 4)

The number 18446744073709551615 is -1 written as an unsigned 64-bit number. The at function takes an unsigned index, so -1 becomes that very large value, which is outside the vector. The exit code is 134, which means the program was stopped by an abort signal.

If the code had used ways[i - 2] instead, there would be no message. The program would read memory before the start of the vector. That is undefined behavior, which means C++ sets no rules for the result: the program may print a meaningless number, crash later, or seem to work. That is why .at() is useful while debugging.

Bug 2: a bad fill order

The second program counts paths in a grid. A robot starts at the top-left corner and can move right or down. It must reach the bottom-right corner. The number of paths to each cell is the number of paths to the cell above plus the number of paths to the cell to its left.

The program keeps one row of counts instead of the whole table. This is the rolling row method. Each entry row[c] holds the number of paths to column c in the current row. Before the first update, the top row is all ones, because there is only one way to walk along a single row.

When the program updates column c of row r, the two values it needs are:

• row[c], which still holds the value from the row above. That is the cell above.
• row[c - 1], which holds the value for the current row if it was updated first. That is the cell to the left.

The correct loop goes from left to right, so row[c - 1] is already updated when row[c] is computed. The buggy loop goes from right to left. When it updates row[c], the value in row[c - 1] is still the one from the row above, not the current row. The cell to the left is read too early.

Trace the 3 by 3 grid by hand. Row 0 is 1 1 1. Row 1 is computed from it.

With the correct order:

• column 1: above is 1, left is 1, so the value is 2.
• column 2: above is 1, left is the new 2, so the value is 3.
• Row 1 is 1 2 3.

With the buggy order:

• column 2 is updated first: above is 1, left is the old value 1, so the value is 2.
• column 1: above is 1, left is 1, so the value is 2.
• Row 1 is 1 2 2.

The buggy value for column 2 is 2, but it should be 3, because the cell to its left should carry the value 2 from the current row. The mistake carries into later rows, and the program prints 4 for the 3 by 3 grid. The correct answer is 6, which is C(4, 2), the number of ways to choose which two of the four moves are downs. The output also shows the 3 by 4 grid, where the buggy version gives 4 and the correct answer is 10.

The 2 by 2 grid gives the right answer in both versions, because there is only one column to update in each row, so the direction does not matter. A test on the smallest grid can therefore pass, and the bug only shows up on larger grids. Use at least a 3 by 3 grid for this kind of check.

The fix is the loop direction. Nothing else changes.

Bug 3: zero used as a sentinel

The third program finds the fewest jumps needed to reach the last index. The input is a list of numbers. nums[i] is the longest jump you may make from index i, so from index 1 with nums[1] = 3 you can land on index 2, 3 or 4. The start is index 0, and the goal is the last index. If the goal cannot be reached, the answer should be -1.

The table dp[i] holds the fewest jumps needed to reach index i. Here the table needs a way to say "not reached". That value is a sentinel: a value that is never a real answer, so the program can recognise it.

The buggy program uses 0 as the sentinel. The problem is that 0 is a real answer. dp[0] = 0 is correct, because index 0 needs zero jumps to be reached. So the program cannot tell "reached in zero jumps" from "not reached".

The program makes this worse in two places.

First, it reads dp[j] for every earlier index j, even when j was not reached. If dp[j] is 0 because it was never set, the program takes 0 + 1 = 1 as a candidate. That claims index i can be reached in one jump from an index that cannot be reached at all.

Second, when no earlier index reaches i, dp[i] keeps its 0 value. The program then returns 0 for the last index, which means "zero jumps", even though the last index cannot be reached.

Trace nums = {1, 0, 2}:

• dp[0] = 0. Index 0 jumps 1, so it reaches index 1.
• dp[1] = 1, correct.
• Index 2 cannot be reached. Index 0 reaches only index 1. Index 1 has jump length 0, so it reaches only itself. So dp[2] should stay "not reached".
• The buggy program never sets dp[2], so it stays 0. It returns 0.

Trace nums = {1, 0, 5, 1, 1}:

• Index 2 cannot be reached, as before. Its dp value stays 0.
• Index 2 has jump length 5, so it reaches index 3 and index 4 in the buggy program. The candidate for index 3 is dp[2] + 1 = 0 + 1 = 1.
• So the program says index 4 can be reached in 1 jump, but nothing reaches index 2.

The output shows both cases: buggy=0 and buggy=1 where the correct answer is -1 in both.

The fix has two parts. Use -1 as the "not reached" sentinel, because -1 can never be a real number of jumps. Then skip any j whose dp[j] is -1. The fixed function does this, and it also sets dp[0] = 0 explicitly, so index 0 is a real starting value and not a sentinel.

The fixed program returns 2 for {2, 3, 1, 1, 4}, which is correct: index 0 jumps to index 1, and index 1 jumps 3 to reach index 4. It returns -1 for the other two inputs.

Common mistakes

Testing only one small input. The base case bug shows up on every input except n = 1, but the 2 by 2 grid hides the fill order bug. Use inputs that are small but not trivial, and check each one by hand.

Changing a sentinel in one place only. The fix for bug 3 changes the initial value and the check. If you change only the initial value to -1 and keep the check dp[i] == 0, the program still gives wrong answers. Search for every place the sentinel is written and read.

Trusting a clean compile. All three buggy programs compile with -Wall and print no warnings. The compiler checks syntax and some types. It does not check whether the table means what you think it means.

Printing only the final answer. When the answer is wrong, print the table. The grid trace in this lab shows the wrong value appearing in the middle of the table, long before the final answer. A table print finds the bug faster than rereading the code.

Assuming a zero value is "empty". A zero can be a real answer, a real count, or a real cost. Before you use zero as a special value, check whether the problem can produce it.

Practice

Exercise 1: trace the stairs

Trace climb_buggy(3) on paper with ways[0] = 0. Write down each value of ways. What does it return, and what should it return?

Show the answer

The values are ways[0] = 0, ways[1] = 1, ways[2] = 1, and ways[3] = ways[2] + ways[1] = 1 + 1 = 2. It returns 2. The correct answer is 3: one step then two steps, two steps then one step, or three one-steps. The program prints n=3 buggy=2 fixed=3.

Exercise 2: fix the grid by changing one thing

Change only the loop direction in grid_paths_buggy so that it becomes correct. Predict the answer for a 3 by 4 grid before you run it. What is the number of paths?

Show the answer

Change for (int c = cols - 1; c >= 1; --c) to for (int c = 1; c < cols; ++c). For a 3 by 4 grid the answer is 10. The row values are 1 1 1 1, then 1 2 3 4, then 1 3 6 10. You can also check it with the binomial count C(5, 2) = 10, since a 3 by 4 grid needs 2 downs and 3 rights in some order.

Exercise 3: the edges of the jump program

What does min_jumps_fixed return for {0, 1}, and for {5}? Explain each answer from the code, without running it.

Show the answer

For {0, 1}, index 0 has jump length 0, so it cannot reach index 1. The value dp[1] stays -1, and the function returns -1. For {5}, there is only one index, which is index 0, and dp[0] = 0. The function returns dp[n - 1], which is dp[0], so it returns 0. Zero jumps is correct, because you are already at the last index.

Exercise 4: why the memo is still correct

A memoized function counts paths and stores results in a table. Its memo table starts at 0, and the code treats 0 as "not computed yet". Some inputs have a true count of 0, such as a cell that cannot be reached. Does this give a wrong answer, or only slow work? Explain.

Show the answer

It gives correct answers, but it does extra work. A cell whose true count is 0 looks "not computed" each time it is asked for, so the function computes it again. The recomputed value is still 0, so the totals are right. The same zero would give a wrong answer if the program used it to mean "unreachable" inside a minimum, as the jump program does. The fix for the slow case is a separate flag, or a sentinel such as -1 that a count can never be.

Exercise 5: read the crash message

The message in the crash example says __n (which is 18446744073709551615). Why is the index this large, and what value should the index have had?

Show the answer

The index is i - 2 with i = 1, which is -1. The function takes an unsigned index, and -1 written as an unsigned 64-bit number is 2 to the power 64 minus 1, which is 18446744073709551615. The index should have been 0 or more. The fix is to start the loop at i = 2, or to handle the first two cases before the loop.

Summary

• Check base cases first by writing down the stored value for the smallest inputs.
• A wrong loop direction can make a cell read an old value, which gives wrong answers that look plausible.
• A sentinel must be a value that can never be a real answer, such as -1 when the answer is never negative.
• Trace a tiny input by hand, print the table, and compare cell by cell.
• Use .at() while debugging, so a bad index throws an error instead of reading garbage.