Most common dynamic programming mistakes

Most engineers assume their dynamic programming mistakes come from coding bugs. An off-by-one error, a missing edge case, something in the implementation. It's almost never the implementation.

What makes dynamic programming mistakes different

Dynamic programming mistakes are formulation errors, not coding bugs. All five of the most common ones happen before you write a single line of code. That's what makes them maddening.

When a sorting algorithm has a bug, you can trace through the comparisons and find the broken step. When a graph traversal visits the wrong node, you can print the adjacency list and spot the error. Standard debugging works for these because the problem is in the code.

DP doesn't work that way. Your code compiles, runs, and produces an answer. The answer is just wrong. And the reason isn't in any line you wrote. It's in the formulation you chose before writing anything.

Debugging implementation errors is like proofreading a sentence for grammar. Debugging formulation errors is like realising you answered the wrong question entirely.

The instinct to debug code line by line runs deep. You've spent years building it. But DP is one of the few areas where that instinct actively misleads you, because the error sits one layer above the code.

Defining the wrong state

The most common DP mistake, and the hardest to catch. You define dp[i] to represent something that sounds right but doesn't capture what you actually need.

The Longest Increasing Subsequence problem makes this concrete. Given an array like [10, 9, 2, 5, 3, 7, 101, 18], you need the length of the longest strictly increasing subsequence.

Most people's first instinct is "let dp[i] be the length of the longest increasing subsequence in the subarray [0..i]." Sounds reasonable. But it isn't workable. dp[i] defined this way doesn't give you enough information to compute dp[i+1], because extending an increasing subsequence requires knowing what value it ends with. A subsequence of length 4 ending at 7 can be extended by 101. A subsequence of length 4 ending at 101 can't be extended by 18. The "LIS of the subarray" definition loses that critical piece.

The correct state is that dp[i] represents the length of the longest increasing subsequence ending at index i.

You can't apply a universal rule that says "always define state as ending at index i." Knapsack uses dp[i][w] for "max value using items [0..i] with capacity w." Coin Change uses dp[i] for "minimum coins to make amount i." Each problem demands a state definition that encodes enough information for the transitions to work. The only real test is whether the recurrence relation follows naturally from what you defined.

Missing or incorrect base cases

Base cases are the foundation of the recurrence. Get them wrong and every value in the table is off. Sometimes the error is consistent enough to stay invisible on small inputs.

This one is sneaky.

Consider Coin change. You need the minimum coins to make amount n from denominations [1, 3, 4]. The recurrence says dp[i] = min(dp[i - coin] + 1) for each valid coin. But what are the base cases?

You need dp[0] = 0, because zero coins make amount zero. Miss this and the recurrence has nothing to build from. You also need dp[i] = infinity for all i greater than 0 initially. Set these to 0 instead and the min operation produces garbage, because it treats every amount as already achievable for free.

That second one catches people because it doesn't feel like a "base case" in the traditional sense. But DP treats initialisation and base cases identically. The recurrence can't tell whether a value was set by a base case or by a previous transition. If the initial value is wrong, the transitions propagate the error silently.

Wrong transition direction

You've defined the state correctly and the base cases are right, but your code fills the table in the wrong order. The values it reads haven't been computed yet.

This happens when the dependency direction of the recurrence doesn't match the iteration order. For Edit Distance between two strings, dp[i][j] depends on three cells: dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. Each cell needs the cell above, to the left, and diagonally above-left. So you fill left-to-right, top-to-bottom. Reverse the direction and dp[i][j-1] hasn't been computed when you try to read it.

For 1D problems the mistake is subtler. In Coin Change, dp[i] depends on smaller indices, so you iterate forward. But in Longest Palindromic Subsequence, dp[i][j] depends on dp[i+1][j-1]. Row i+1 must be filled before row i, so you iterate the rows backward.

Before writing any loop, draw the dependency arrows. If cell (i, j) depends on cell (i+1, j-1), then i must decrease and j must increase in your iteration order. Skip this step and you'll produce answers that look plausible but are wrong in ways that are extremely hard to trace.

Confusing mistakes from pattern similarity

Longest Common Subsequence and Longest Increasing Subsequence share three words in their names. They use different state definitions, different transitions, and different final answers.

The confusion runs deeper than names. Both involve subsequences, both are classic DP problems. But the structure is different. LCS compares two sequences and asks what they share. LIS examines one sequence and asks about internal ordering. Those structural differences drive every difference in the formulation.

The same thing happens with Subset Sum and Coin Change. Both involve sums and sets of values, but Subset Sum is a boolean problem (dp[i][w] = true or false) while Coin Change is an optimisation problem (dp[i] = minimum count). The transitions, base cases, and final answers are all different because the underlying question is different.

Returning the wrong final answer

The final answer in DP isn't always dp[n] or dp[m][n]. Sometimes the answer is scattered across the entire table and you need to search for it.

You already saw this with LIS, where the answer is max(dp[0..n]) rather than dp[n]. dp[n] only gives you the longest increasing subsequence ending at the last element, which may not be the longest one overall.

The same variation shows up elsewhere. For Longest Palindromic Subsequence on a single string, the answer is dp[0][n-1], the full string range. Rod Cutting is straightforwardly dp[n] for a rod of length n. Minimum Path Sum on a grid lands at dp[m-1][n-1], the bottom-right corner.

The principle is simple. The final answer lives wherever your state definition says "the quantity I actually want." If dp[i] means "LIS ending at i," then the global LIS is the maximum over all dp[i] values. If dp[i][j] means "edit distance for first i chars and first j chars," then the full edit distance is dp[m][n]. Read your own state definition and ask whether the cell you're returning actually answers what the problem asked.

The fix that prevents all five

These five mistakes share a root cause: the engineer jumped to code before finishing the formulation. The formulation has four steps, and they need to happen in order.

Skip any step or do them out of order and you get exactly the five mistakes in this article. Wrong state: step 1 was skipped. Missing base cases: step 3 was skipped. Wrong transition direction: step 2 was done without drawing dependencies. Pattern confusion: step 1 was borrowed from a different problem. Wrong final answer: step 4 was assumed instead of derived.

This four-step derivation is how Codeintuition's Dynamic Programming course teaches every DP pattern. You derive the recurrence from the state definition before attempting Coin Change. You draw the dependency arrows before attempting LCS. The formulation comes first, and the code follows from it. Across 38 problems and 5 pattern families, each problem reinforces the same derivation sequence until it becomes automatic.

For the full progression from identifying whether a problem needs DP through building the recurrence from scratch, see our complete guide to dynamic programming.

Codeintuition's learning path covers all the prerequisite structures before DP, so the reasoning tools are already in place when you reach the hardest pattern family. The free Arrays and Singly Linked List courses give you 63 lessons and 85 problems to test the formulation-first approach on simpler patterns before committing to premium at $79.99/year.

The next time a DP solution gives you the wrong answer, don't reach for the debugger. Go back to your state definition. Read it carefully and ask whether it encodes enough information for the transitions to work. If it doesn't, no amount of line-by-line tracing will find the problem. The problem was never in the lines.