Dynamic Programming Bugs That Pass Every Obvious Test Case

The worst kind of bug is the one your code runs through without complaint. DP failures are rarely crashes. They're wrong numbers, plausible-looking, produced at full speed, returned with no error message. You test with the examples and they pass. You submit. Wrong answer.

Congratulations. Your bug has excellent test coverage.

This happens because dynamic programming bugs are logical, not syntactic. The code is valid. The algorithm structure is correct. One detail is off, and that detail corrupts every value in the table silently. Six categories cover almost everything you'll encounter in an interview.

Your State Definition Isn't Holding Enough

The most common root cause in DP: your state doesn't capture all the information the recurrence actually needs.

Classic example. Longest Common Subsequence. You define dp[i] = length of LCS ending at index i in s1. That makes sense locally. Then you try to write the recurrence and can't, because you've thrown away where you are in s2. The state remembered half the problem and forgot the other half.

The fix is dp[i][j] = length of LCS considering the first i characters of s1 and the first j characters of s2:

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Your state must uniquely identify the subproblem. Everything required to compute a cell's value must either be in the state index or be a constant from the input.

The practical test: can you write the recurrence entirely in terms of the state variables and the inputs, with no "I also need to remember X"? If you find yourself needing hidden context, add a dimension.

A subtler version shows up in problems with interacting constraints. Consider a grid with obstacles where you can remove exactly one. dp[i][j] = number of paths to cell (i, j) works fine until that removal rule. Now you need dp[i][j][k] where k is 0 or 1 tracking whether you've used your obstacle removal. Miss that dimension and the recurrence writes nonsense into every cell, confidently.

You Initialized for the Average Case, Not the Edge Cases

Three classic problems, three different wrong initializations. All look fine on standard inputs. All fail on inputs that are annoyingly real.

Kadane's algorithm (Maximum Subarray). The tempting version:

current = 0
global_max = 0
for num in nums:
    current = max(num, current + num)
    global_max = max(global_max, current)
return global_max

Try it on [-3, -1, -2]. Returns 0. The correct answer is -1. Initializing with 0 implicitly allows the empty subarray, but LeetCode 53 requires at least one element. Your algorithm picked the invisible empty subarray and declared victory.

Fix: initialize both to nums[0], start the loop at index 1.

LIS (Longest Increasing Subsequence). dp[i] represents the length of the LIS ending at index i. Every single element forms a valid subsequence of length 1 by itself, so the correct initialization is all ones. Initialize to zeros and dp[i] starts at zero, which means the base case "a single element" is broken before you write a single transition.

dp = [1] * len(nums)  # not [0] * len(nums)

Input [5] returns 0 with the wrong initialization. It should return 1. The subsequence is right there. It's the only element in the array. Zero is wrong.

Coin change (minimum coins). dp[amount] = fewest coins to reach that amount. You need an explicit "unreachable" sentinel for every amount you haven't proven reachable yet. Zero is a valid answer (the empty set), so it's wrong as a starting placeholder.

dp = [float('inf')] * (amount + 1)
dp[0] = 0

Initialize everything to 0 and fail to reach some amount: you'll return 0 instead of -1. Your code just told the judge you reached an unreachable amount in zero coins.

The right initialization encodes the base case explicitly. "Zero by default" is not a base case.

Diagnostic: before writing transitions, trace through a single-element input or the smallest non-trivial case by hand. If that first cell is wrong, stop and fix the initialization.

You're Returning the Last Cell When You Need the Maximum

Two problems with nearly identical structure and completely different return values. Getting this wrong has the same energy as answering a different question than the one you were asked.

House Robber. dp[i] = maximum amount you can rob from houses 0 through i:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

This state accumulates. dp[i] always represents the best outcome across all previous houses. The answer at the end of the array is the global optimum. Return dp[n-1].

LIS. dp[i] = length of the longest increasing subsequence ending exactly at index i:

for j in range(i):
    if nums[j] < nums[i]:
        dp[i] = max(dp[i], dp[j] + 1)

This state is local. dp[i] only knows about subsequences that happen to terminate at position i. For input [1, 3, 2], the LIS is [1, 3] and it ends at index 1, not index 2. dp[2] = 2 (the subsequence [1, 2]), dp[1] = 2 (the subsequence [1, 3]). Return max(dp).

If your state means "the best solution up to and including position i," return the last element. If it means "the best solution that ends exactly at position i," return the maximum across all positions.

Other problems that need max(dp): Maximum Product Subarray, LIS variants, longest palindromic subsequence starting or ending at each index. The diagnostic question: is there any input where the optimal answer ends before the last element? If yes, you need max(dp).

Your 2D Table Is One Index Off Everywhere

In edit distance, LCS, and most 2D DP problems, you build a table of size (m+1) x (n+1). The extra row and column hold the base cases for empty prefixes. Your loop runs for i in range(1, m+1). But Python strings are 0-indexed.

Wrong:

if word1[i] == word2[j]:     # wrong: gets the (i+1)-th character
    dp[i][j] = dp[i-1][j-1]

Right:

if word1[i-1] == word2[j-1]: # correct: i-th prefix ends at index i-1
    dp[i][j] = dp[i-1][j-1]

When i=1, you want the first character of word1, which is word1[0]. Using word1[i] gets the second character instead. This is a silent bug. No index error, just wrong answers, consistently wrong, for every non-trivial input.

It fails quietly because the array is large enough that word1[i] never goes out of bounds. It just reads the wrong character, every time. Each cell in the table builds on that shifted read, and the error propagates through the entire dp array without raising a single exception.

How to catch it: before coding, write out the table header. Row i=1 corresponds to character word1[0]. Column j=1 corresponds to character word2[0]. If that mapping isn't explicit in your index access, your character lookups are off. The LCS and edit distance walkthrough covers the full 2D table structure.

You're Scanning the Knapsack Forward and Counting Everything Twice

The space-optimized 0/1 knapsack:

dp = [0] * (capacity + 1)
for weight, value in items:
    for w in range(capacity, weight - 1, -1):  # backward, not forward
        dp[w] = max(dp[w], dp[w - weight] + value)

That backward direction isn't a convention. It's a requirement.

If you iterate forward, when you compute dp[w], you read dp[w - weight]. But that cell was just updated earlier in this same pass, with this same item already counted. You've packed the same item into the knapsack twice. Congrats, you just invented the unbounded knapsack.

Backward iteration preserves the semantics of the previous row. Here's why. The full 2D version is:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight] + value)

Row i reads from row i-1. When you collapse to 1D, both rows share the same array. Reading right to left means when you compute dp[w], the cell dp[w - weight] (which comes earlier in the array) hasn't been updated yet this pass. It still holds the i-1 value. Reading left to right overwrites it first.

Backward iteration isn't a trick. It's what the 2D-to-1D reduction requires when each item can be used at most once. Unbounded knapsack (items usable unlimited times) deliberately iterates forward, because reuse is allowed. The knapsack pattern breakdown covers the full 2D table.

Your Loops Are Swapped, and You're Solving the Wrong Problem

Coin Change II (LeetCode 518): count the number of combinations that make up the amount. Order doesn't matter, so {1, 2, 2} and {2, 1, 2} are the same.

dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:                       # outer: coins
    for w in range(coin, amount + 1):    # inner: amounts
        dp[w] += dp[w - coin]

Now swap the loops:

dp = [0] * (amount + 1)
dp[0] = 1
for w in range(1, amount + 1):          # outer: amounts
    for coin in coins:                   # inner: coins
        if w >= coin:
            dp[w] += dp[w - coin]

Both compile. Both run fast. For coins = [1, 2, 5] and amount = 5, version one returns 4. Version two returns 9.

That 9 is not a random wrong number. It is the exact answer to LeetCode 377 (Combination Sum IV), which counts ordered arrangements where [1, 2, 2] and [2, 1, 2] are considered distinct. The swapped-loop version is a correct solution. To the wrong problem. This is the most demoralizing DP bug because your code is completely correct and you will never find the mistake by debugging it.

The mechanism: coins as the outer loop means you pick each denomination and process it fully before moving to the next. You'll never revisit coin 1 after advancing to coin 2, so you'll never count [1,2] and [2,1] separately. Amounts as the outer loop means at each target value you try all coins simultaneously, rediscovering every ordering you already counted.

To verify which version you wrote: try coins = [1, 2], amount = 3. Combinations are {1,1,1} and {1,2}, two ways. Permutations are {1,1,1}, {1,2}, {2,1}, three ways. If your code returns 3, your loops are swapped. The coin change problem walkthrough has more on why the recurrence looks nearly identical across both variants.

Six Dynamic Programming Bug Checks Before You Submit

Run through this before you finalize any DP solution:

State completeness: can the recurrence be written purely in terms of the state variables? No hidden context needed?
Initialization: test on a single-element input; test on all-negative or all-zero inputs
Return value: does the state accumulate to the end (return last) or measure a local property (return max)?
2D indexing: if dp[i][j] is 1-indexed, are string accesses offset by one (s[i-1])?
Knapsack direction: 0/1 = backward; unbounded = forward
Loop order in counting problems: combinations = coins outer; permutations = amounts outer

Most DP failures are one of these six. None of them crash. All of them produce plausible wrong answers. A quick trace through a simple case reveals them in thirty seconds.

SpaceComplexity runs voice-based DP interviews where you explain your state definition and recurrence out loud before coding. The rubric feedback scores exactly this class of logical error, not just whether the final answer matches.