13.24 Testing Dynamic Programming Algorithms

Dynamic programming algorithms are especially prone to subtle bugs. A wrong base case, an off-by-one error, a bad iteration order, or an accidentally reused state can produce answers that look correct on small samples and fail later.

Testing DP requires more than checking the examples in a problem statement. Good tests should exercise boundaries, unreachable states, tie cases, reconstruction behavior, and equivalence between slow and optimized implementations.

This section gives a practical testing strategy for dynamic programming code.

Problem

How do we test dynamic programming algorithms so that recurrence errors, indexing mistakes, and optimization bugs are caught early?

Start with the State Contract

Every test should be tied to the state meaning.

If your state is:

$$ dp[i][j] $$

meaning:

minimum edit distance
between first i characters of A
and first j characters of B

then tests should include:

empty prefixes

single-character prefixes

equal strings

completely different strings

strings requiring insertion

strings requiring deletion

strings requiring replacement

State definitions imply boundary cases.

Use them to design tests.

Test Base Cases First

Base cases are the anchor of every DP table.

Examples:

Fibonacci

if Fib(0) != 0 {
    t.Fatal("Fib(0)")
}

if Fib(1) != 1 {
    t.Fatal("Fib(1)")
}

Edit Distance

if EditDistance("", "") != 0 {
    t.Fatal("empty strings")
}

if EditDistance("", "abc") != 3 {
    t.Fatal("insert all")
}

if EditDistance("abc", "") != 3 {
    t.Fatal("delete all")
}

If base cases are wrong, larger cases are usually meaningless.

Test Small Inputs Exhaustively

For small inputs, brute force is often simple enough to implement.

Example:

• generate all subsets for knapsack
• generate all subsequences for LIS
• enumerate all paths in a tiny DAG
• recursively compute edit distance without memoization

Then compare the DP result against the brute-force result.

This is one of the most effective ways to test dynamic programming.

Example: Testing Knapsack Against Brute Force

func BruteKnapsack(
    weights []int,
    values []int,
    capacity int,
) int {

    n := len(weights)
    best := 0

    for mask := 0; mask < (1 << n); mask++ {

        weight := 0
        value := 0

        for i := 0; i < n; i++ {

            if mask&(1<<i) != 0 {
                weight += weights[i]
                value += values[i]
            }
        }

        if weight <= capacity && value > best {
            best = value
        }
    }

    return best
}

Then compare:

func TestKnapsackSmall(t *testing.T) {

    weights := []int{2, 3, 4}
    values := []int{3, 4, 5}

    for capacity := 0; capacity <= 10; capacity++ {

        got := Knapsack(
            weights,
            values,
            capacity,
        )

        want := BruteKnapsack(
            weights,
            values,
            capacity,
        )

        if got != want {
            t.Fatalf(
                "capacity=%d got=%d want=%d",
                capacity,
                got,
                want,
            )
        }
    }
}

The brute-force implementation does not need to be fast. It only needs to be clear and correct for small sizes.

Randomized Differential Testing

Once a brute-force oracle exists, use random tests.

func TestKnapsackRandom(t *testing.T) {

    rng := rand.New(
        rand.NewSource(1),
    )

    for test := 0; test < 1000; test++ {

        n := 8
        capacity := rng.Intn(20)

        weights := make([]int, n)
        values := make([]int, n)

        for i := 0; i < n; i++ {
            weights[i] = 1 + rng.Intn(10)
            values[i] = rng.Intn(30)
        }

        got := Knapsack(
            weights,
            values,
            capacity,
        )

        want := BruteKnapsack(
            weights,
            values,
            capacity,
        )

        if got != want {
            t.Fatalf(
                "got=%d want=%d weights=%v values=%v capacity=%d",
                got,
                want,
                weights,
                values,
                capacity,
            )
        }
    }
}

This style catches errors that hand-picked examples often miss.

Use a fixed seed so failures are reproducible.

Compare Optimized and Unoptimized Versions

Memory compression and transition optimization introduce new failure modes.

For example, 0/1 knapsack with one-dimensional storage is easy to break by iterating capacity in the wrong direction.

Write both versions:

clear full-table implementation

optimized implementation

Then compare them on many small inputs.

got := KnapsackCompressed(weights, values, capacity)
want := KnapsackFullTable(weights, values, capacity)

The full-table implementation acts as a reference.

This is especially important for:

• rolling arrays
• bitset compression
• convex hull trick
• divide-and-conquer DP
• Knuth optimization

Test Iteration Direction

Some bugs are specifically caused by overwriting states too early.

For 0/1 knapsack, this input exposes forward-iteration bugs:

weights = [2]
values  = [10]
capacity = 4

Correct answer:

10

If the algorithm returns:

20

it has accidentally solved unbounded knapsack.

This is a small but powerful test.

Test Unreachable States

Optimization DP often uses sentinel values.

For coin change:

coins = [5]
target = 3

Expected result:

-1

or whatever convention the API uses for unreachable.

Tests should verify that impossible states remain impossible.

if MinCoins([]int{5}, 3) != -1 {
    t.Fatal("unreachable amount should return -1")
}

Sentinel handling bugs commonly appear only in unreachable cases.

Test Ties

Many DP algorithms have multiple optimal solutions.

For example:

weights = [2, 2]
values  = [5, 5]
capacity = 2

There are two equally good choices.

If the function returns only the optimal value, tie behavior does not matter.

If it reconstructs selected items, tie behavior must be specified.

Tests should verify the chosen policy:

first valid solution

lexicographically smallest solution

any optimal solution

Avoid writing tests that accidentally require an unspecified tie policy.

Test Reconstruction Separately

When reconstructing a path, subsequence, edit script, or item selection, verify two properties:

1. The reconstructed solution is valid.
2. Its value equals the DP optimum.

For LCS, do not merely compare against one expected string. There may be many correct LCS strings.

Instead test:

is subsequence of A

is subsequence of B

length equals LCS length

This avoids rejecting valid alternative answers.

Example: Validating an LCS Result

func IsSubsequence(s, t string) bool {

    i := 0

    for j := 0; j < len(t) && i < len(s); j++ {

        if s[i] == t[j] {
            i++
        }
    }

    return i == len(s)
}

A reconstruction test can check:

lcs := BuildLCS(a, b)

if !IsSubsequence(lcs, a) {
    t.Fatal("not subsequence of a")
}

if !IsSubsequence(lcs, b) {
    t.Fatal("not subsequence of b")
}

if len(lcs) != LCSLength(a, b) {
    t.Fatal("wrong length")
}

This tests the contract rather than one arbitrary output.

Test Boundary Sizes

Include tests for:

empty input

one element

two elements

maximum capacity zero

single row or column

single node tree

disconnected DAG components

Dynamic programming code frequently handles interior states correctly and fails at boundaries.

Test Numeric Limits

Counting DP and optimization DP can overflow.

Tests should include large enough inputs to expose overflow risks.

Examples:

number of paths in a large grid

number of subsequences

large coin-change counts

large weights and values

If results are computed modulo (M), verify that the modulus is applied during updates, not only at the end.

Test Monotonicity Assumptions

Optimized DP techniques often depend on hidden structural assumptions.

For divide-and-conquer DP, test whether:

$$ opt(i) \le opt(i+1) $$

holds for generated cases.

For Knuth optimization, test whether:

$$ opt[l][r-1] \le opt[l][r] \le opt[l+1][r] $$

holds for small cases.

For convex hull trick, compare the optimized hull query result against a naive scan of all lines.

When an optimization relies on an invariant, test the invariant directly.

Print Tables During Debugging

For small examples, a DP table is often the best diagnostic tool.

Example:

Edit distance table
LCS table
Knapsack table
Grid path table

A single wrong row or column usually reveals:

bad initialization

wrong recurrence

wrong iteration order

Debug output should be removed or gated behind a flag, but during development it is invaluable.

Property-Based Test Ideas

Many DP problems have useful algebraic properties.

Edit Distance

distance(a,b) == distance(b,a)
distance(a,a) == 0
distance(a,b) >= abs(len(a)-len(b))

LCS

LCS(a,b) <= min(len(a), len(b))
LCS(a,a) == len(a)

Knapsack

answer does not decrease
as capacity increases

Grid Paths

paths(m,n) == paths(n,m)

These properties do not replace exact tests, but they catch broad classes of mistakes.

A Testing Checklist

For every DP algorithm, test:

1. Base cases.
2. Small exhaustive cases.
3. Random cases against brute force.
4. Unreachable states.
5. Boundary sizes.
6. Tie cases.
7. Reconstruction validity.
8. Optimized version against reference version.
9. Numeric limits.
10. Invariants required by advanced optimizations.

This checklist is practical. It catches most DP failures before they reach production or contest submission.

Takeaway

Dynamic programming algorithms should be tested against their state contract, not just against sample inputs. Start with base cases, use brute force as an oracle for small inputs, compare optimized versions against simple reference implementations, and test reconstruction by validating output properties rather than assuming one canonical answer. For advanced optimizations, test the structural invariants that justify the optimization. A disciplined testing strategy turns dynamic programming from a fragile table-filling exercise into a reliable engineering practice.