How to derive DP recurrence relations

Most engineers can read a DP recurrence and follow the logic. dp[i] = dp[i-1] + dp[i-2] makes sense once you see it. But ask them to derive the recurrence for a problem they haven't seen, and they freeze. The knowledge is there. What's missing is a repeatable process for applying it. Learning how to derive DP recurrence relation formulas from scratch turns unfamiliar problems into tractable ones, and the process is more mechanical than you'd expect.

What a DP recurrence relation actually means

A DP recurrence relation is a formula that expresses the optimal solution to a problem in terms of optimal solutions to smaller subproblems. You don't invent it. You derive it by defining what your state represents, then asking how the answer for the current state extends from answers you've already computed.

Most explanations skip that part entirely. They show the recurrence and explain why it's correct, but they don't show how you'd arrive at it if you'd never seen the problem before.

Every DP recurrence answers the same question. "If I already know the answer to a smaller version of this problem, what's the minimum additional information I need to extend it?" The recurrence translates that question directly into code.

That extension question sits at the core of every DP derivation.

Take Fibonacci as the simplest case. The state dp[n] represents the nth Fibonacci number. The extension question is straightforward because the nth number is just the sum of the two before it. So dp[n] = dp[n-1] + dp[n-2], with base cases dp[0] = 0 and dp[1] = 1.

That derivation feels obvious for Fibonacci. But the process is identical for Longest Common Subsequence, Edit Distance, and Knapsack. The problems are harder, but the reasoning pattern is the same. Defining the right state is the hard part, not the recurrence formula itself.

Why memorizing recurrences doesn't work

Most DP study follows a predictable loop. You read a problem, get stuck, look up the solution, see the recurrence, understand why it works, and move on. Do this 50 times and you'll recognise many common recurrences on sight.

But recognition is near-transfer. It works when the new problem looks similar to one you've practised. It fails when it doesn't.

Interviews test the opposite skill. You get a problem you haven't seen, and you need to construct the recurrence from the problem's structure. That's far-transfer, and it requires a different kind of practice entirely. You can't get there by memorizing formulas any more than you can learn to write essays by memorizing sentences.

The gap between "I understand this recurrence" and "I could have derived it" is where most engineers get stuck on DP. Closing that gap takes a repeatable process, not more examples to memorize.

Some DP problems genuinely have non-obvious recurrences, though. Matrix Chain Multiplication and Boolean Parenthesization have state definitions that aren't intuitive even with experience. The derivation process still applies, but these problems need more experimentation with different state definitions before you land on the right one. You won't always get a clean derivation on the first attempt, and that's expected.

Three steps to derive any DP recurrence relation

Every DP recurrence relation comes from three decisions, made in sequence. Skip a step or do them out of order, and the recurrence either breaks or never materializes.

Step 1: Is where most engineers fail. They jump straight to writing the transition before defining what their state variable represents. Without a clear state definition, the transition has nothing to reference.

A good state definition answers a precise question. Not "something about the first i elements" but "the length of the longest increasing subsequence ending at index i" or "the minimum number of coins needed to make amount j." The more precise your question, the more naturally the transition follows.

Step 2: Is where the choices live. At each state, you ask what your options are. For coin change, you can pick any coin denomination. For LCS, you either match the current characters or skip one. Each choice maps to a smaller subproblem, and the transition takes the best result among them.

Step 3: Is often trivial but easy to forget. Base cases are the states where no further recursion is needed. Usually they represent empty inputs, zero-length sequences, or amounts of zero. Getting them wrong means the recurrence produces incorrect results even when the transition is perfect.

How to derive the LCS DP recurrence relation

Let's derive the recurrence for Longest Common Subsequence from scratch, using all three steps. We won't peek at the formula and will rely only on the reasoning.

The problem is to find the length of the longest common subsequence of two strings s1 and s2.

Start with step 1 and define the state. You need a state that captures progress through both strings. A single index won't work because the answer depends on how far you've processed each string independently. So define dp[i][j] as the length of the longest common subsequence of the first i characters of s1 and the first j characters of s2. You need two dimensions because you're tracking position in two separate strings.

This is where many engineers go wrong. They try a 1D state like "longest subsequence involving index i" and get stuck because it doesn't account for the second string.

Step 2 is the transition. You're at position i in s1 and position j in s2. You need to ask what your choices are at this point.

Two cases come up, and each one maps directly to a recurrence expression.

If the current characters match (s1[i-1] equals s2[j-1]), this character can extend the LCS. The best you can do is take whatever LCS you had for the first i-1 and j-1 characters, plus this match. Matching characters always contribute to the common subsequence, so you take the previous best and add one:

dp[i][j] = dp[i-1][j-1] + 1

If they don't match, you can't extend. But you can keep the best LCS found so far by either advancing past the current character in s1 or in s2. The recurrence picks whichever option gives a longer subsequence:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Notice where the transition came from: asking "what are my choices at this state?" Not pattern matching against a memorized formula.

Step 3 covers the base cases. If either string is empty (i equals 0 or j equals 0), the LCS is 0. There's no common subsequence between an empty string and anything.

This same three-step process applies to Edit Distance, Knapsack, and every other DP pattern on the Dynamic Programming course. Problems differ, but the reasoning stays the same: define the state precisely, enumerate your choices, pick the best, anchor it with base cases.

Common mistakes that break derivations

These are structural missteps, not careless errors. They come from how engineers approach the derivation itself.

The most common is a wrong state definition. You might define dp[i] as "the answer for element i" without specifying what "answer" means. If your state definition is vague, your transition will be vague too. "The longest subsequence involving index i" is different from "the longest subsequence ending at index i," and the wrong choice produces the wrong recurrence.

Another common mistake is missing dimensions. You try to solve a 2D problem with a 1D state. LCS needs two indices because you're tracking two strings. Knapsack needs capacity and item count. If your transition can't reference the right subproblems, you're probably missing a dimension in your state.

Engineers also skip base case validation. You derive a clean transition, fill in the table, and get wrong answers. Usually it's a base case issue, so trace through the smallest inputs (empty strings, zero amount, single element) and verify the base cases produce correct results before trusting the rest.

Not testing the transition on small inputs before coding is equally common. Before writing the full implementation, trace the recurrence on a 2-3 element input by hand. If dp[2][3] doesn't compute correctly from the states it references, the transition has a bug that small inputs expose faster than debugging a full implementation.

Where this fits in the DP puzzle

Deriving recurrence relations is one piece of the DP puzzle. Recognizing when a problem requires DP in the first place is the step before this one. Deciding between memoization and tabulation for implementation is the step after.

For the complete picture on dynamic programming, from problem classification through optimization techniques and all five DP pattern families, see the full guide to dynamic programming for interviews.

This derivation process is how Codeintuition's learning path teaches every DP pattern. Instead of memorizing the recurrence for each problem type, you work through the state definition, transition, and base cases from first principles. The LCS lesson walks through this exact derivation with frame-by-frame visual walkthroughs that trace how each cell in the table fills and why.

Six months ago, you'd see an unfamiliar DP problem and immediately scan for a recurrence you'd memorized. Now you read the problem, define the state, and ask what choices exist at each step. The recurrence follows from the problem's structure, not your memory. That's the difference between solving problems you've practised and solving ones you haven't.

The first time you derive a recurrence cold, without peeking at anything, you won't need anyone to tell you the process works.