DP stops being scary when you name the state

The short version. Dynamic programming (DP) breaks a problem into smaller subproblems, solves each once, and reuses each answer. The win: exponential work collapses to polynomial when you stop recomputing what you already solved.

Richard Bellman named dynamic programming in the mid-1950s to get past a Secretary of Defense who would not fund anything with the word "research" in it. The naming story is in Eye of the Hurricane, Bellman's autobiography. Wikipedia's Dynamic programming article repeats it on page one. The label is historical debris. The technique is not.

Jeff Erickson's Algorithms textbook — free online at jeffe.cs.illinois.edu — spends Chapter 3 (Dynamic Programming) making one claim: DP is not a recursion trick. It is a compression problem. Define a subproblem. Relate it. Order the relations so the dependency graph is acyclic. Fill the table. That is the whole method.

“The one question. What does the future need to know from the past? Answer that and state, recurrence, and iteration order fall out automatically.”

MIT 6.006 — Erik Demaine and Srini Devadas teaching — packages the same sequence as Lecture 15 (SRTBOT, Fib, DAGs, Bowling) and Lecture 16 (LCS, LIS, Coins). Different packaging. Same idea. This post classifies the interview shapes, walks three canonical problems, and hands you off to the textbooks and lectures that do the formal treatment.

The one question

When a problem smells like DP — optimal substructure, overlapping subproblems, "maximum," "minimum," "count," "is it possible" — stop trying to remember a pattern sheet. Ask:

What does the future need to know from the past to make its next decision?

That is the whole move.

If you can say "At position i, the future needs to know X and Y" — your state is probably (i, X, Y). If you can't say that sentence yet, you're not ready to write dp[...].

The common failure mode: start from syntax. Write dp[i] = ..., hope meaning arrives later, call DP "memorization." That is backwards. The strong answer names the trade-off: store just enough past information to make the next decision cheap, but not so much that you explode the state space.

Diagram

Copy source

Rendering diagram...

MIT 6.006 calls this "SRTBOT" — Subproblem, Relation, Topological-order, Base-case, Original-problem, Time-analysis. Erickson makes the same point in textbook form. Both are worth opening side-by-side once.

Climbing Stairs — the cleanest possible state

Warm-up prompt: You are climbing a staircase with n steps. Each move is 1 step or 2. How many distinct ways reach the top?

Ask the question cleanly. At position i, what does the future need to know from the past?

Nothing except i.

That is why this problem is the canonical teaching example. The history of how you got to step i does not matter. The future only needs to know where you are. State is minimal: dp[i] is the number of ways to reach step i.

PYTHON

Copy

def climb_stairs(n): if n <= 1: return 1 dp = [1, 1] + [0] * (n - 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

The dependency graph:

Diagram

Copy source

Rendering diagram...

Each dp[i] depends on dp[i - 1] and dp[i - 2]. Iteration order is not a second mystery — it falls out of the graph. Compute left-to-right because every state depends on earlier states. Erickson's Chapter 3 spends several pages making this formal; the shorthand in interviews is iteration order is the topological order of the dependency DAG.

House Robber — when the state looks bigger than it is

You are robbing houses on a street. Each house has money. You cannot rob two adjacent houses. Return the maximum.

First-pass reach for (i, robbed_last): "I need i, plus a flag for whether I robbed the previous house." That solution works. It is also heavier than necessary.

Ask again: what does the future need to know from the past?

At house i, the future does not care whether house i - 1 was robbed as a separate fact. It cares about the best consistent total through earlier positions. Collapse the flag away.

PYTHON

Copy

def rob(nums): if not nums: return 0 if len(nums) == 1: return nums[0] dp = [nums[0], max(nums[0], nums[1])] + [0] * (len(nums) - 2) for i in range(2, len(nums)): dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]) return dp[-1]

The transition tells the whole story:

• dp[i - 1] — skip house i
• nums[i] + dp[i - 2] — rob house i, best compatible prefix ends at i - 2

A (i, robbed_last) state is sufficient. A plain i state is minimal. Senior interviewers notice the difference — it tells them whether you are deriving the state or hauling information around because it feels safer. NeetCode's House Robber walkthrough spells out the same collapse step-by-step if you want a second pass.

Diagram

Copy source

Rendering diagram...

Same DAG family as Climbing Stairs. Different semantics on the edges. The pattern-recognition skill in DP is not memorizing a catalog — it is learning to compress past decisions into a small, reusable state.

Longest Increasing Subsequence — when the state has to grow up

Given nums, return the length of the longest strictly increasing subsequence.

Example: nums = [10, 9, 2, 5, 3, 7, 101, 18] gives 4.

At index i, knowing i alone is not enough. The future needs the best increasing subsequence length ending at i, because later positions will ask whether they can extend it.

PYTHON

Copy

def length_of_lis(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

This is where candidates confuse the runtime. The state space is still only n. What got expensive is the transition — each dp[i] scans all earlier j, so each state costs O(n) work and the full solution is O(n²).

The useful interview sentence: state count × work per state gives the runtime. Obvious once said. It cleans up a lot of messy complexity-talk in live rounds.

If you want the O(n log n) variant, Wikipedia's LIS article has the patience-sort derivation, and NeetCode's LIS solution covers the canonical interview pitfalls — especially the fact that the binary-search helper array is not the actual subsequence.

The partition model

A DP state partitions the world into decisions already made and decisions still to come.

• Climbing Stairs — "I am at step i."
• House Robber — "I have processed houses through i."
• LIS — "I know the best increasing subsequence ending at i."

The art is compressing the left side of the partition into the smallest thing the right side still needs. That is why DP rhymes with production systems like event replay and retry orchestration — compact state beats reprocessing history.

Top-down vs bottom-up — same math, different failure modes

Two ways of walking the same dependency graph:

• Top-down — recursion plus memoization. Good when the recurrence is easier to write or the reachable state space is sparse.
• Bottom-up — table plus a valid evaluation order. Cleaner when the state space is dense and you do not want stack drama.

Strong answers name the trade-off out loud. They do not pick one by default.

Production DP — git diff is dynamic programming

Every time you run git diff, git runs a DP algorithm on your source file. The implementation lives in xdiff/xdiffi.c inside the xdiff module of git's source. It computes the longest common subsequence using Myers' diff algorithm — a DP solution to LCS with a clever edit-graph optimization. State compression in production is not metaphor. Your terminal uses it hundreds of times a day.

The same shape runs in payment-retry state machines, speech recognition (Viterbi decoding — cited in the Wikipedia article's applications section), genome sequence alignment, and database query planners. Every one of them compresses history into a compact state so the next transition is cheap.

When it is not dynamic programming

DP requires overlapping subproblems. If recursion never revisits the same state, memoization buys you nothing.

• Tree traversals that visit each subtree once
• Divide-and-conquer problems like merge sort
• Problems with a clean greedy proof

The quick test: does this recurrence revisit the same state more than once? If not, DP is extra furniture.

Common mistakes that cost easy points

Writing dp[i] before you can define it in English

"The answer up to i" is not a definition. Name the quantity — ways, max, min, boolean — before the syntax appears.

Carrying state the future does not need

Extra flags feel safe. They usually create bugs and inflate the state space for no gain.

Guessing the base case instead of deriving it

The base case is what the state meaning says the empty-prefix answer should be. Derive it, don't guess.

Filling the table in an order that violates the recurrence

Iteration order is the topological order of the dependency DAG. Draw the DAG if needed.

Never naming the trade-off out loud

"This richer state works, but it doubles the table" — the kind of sentence strong candidates say. Silence here loses points.

The interview talk track

A clean script for a DP round:

1. "This is DP — overlapping subproblems, and I am trying to optimize or count."
2. "The real question is what the future needs to know from the past."
3. "So my state is ..., because that fully summarizes the prefix."
4. "My recurrence is ...."
5. "My base cases are ...."
6. "I fill the table in this order because of those dependencies."
7. "Runtime is state-count × work-per-state."

Seven sentences make a DP answer sound engineered instead of improvised.

Go deeper — the reading list this post is aggregating

For your next DP round, open these in this order:

• Jeff Erickson, Algorithms — Chapter 3 (Dynamic Programming) — free textbook, University of Illinois. The single best free treatment online. Walks DP as compression-of-history from first principles.
• Erik Demaine + Srini Devadas, MIT 6.006 — Lecture 15 (DP Part 1) and Lecture 16 (DP Part 2) — OCW, free. The SRTBOT framework is the cleanest interview-pacing template anywhere.
• Richard Bellman, Eye of the Hurricane — autobiography. The naming-history anecdote is on the chapter where Bellman recounts negotiating with the DoD. Read it once; it kills the mystical-phrase framing permanently.
• Robert Sedgewick, Princeton Algorithms — Substring Search — adjacent DP territory (KMP preprocessing) with working Java code.
• Wikipedia — Dynamic programming, LCS, LIS, Knapsack — reference entries with the formal statements.
• NeetCode (Navdeep Singh), Advanced Algorithms — DP — problem-by-problem walkthroughs covering House Robber, LIS, Coin Change, Edit Distance.
• git's xdiff module — xdiffi.c — production DP running in every git diff invocation. Myers' LCS algorithm in C, heavily commented. Worth reading once to see what state compression looks like outside a coding round.

Read Erickson's Chapter 3 and watch one of the two MIT lectures. That is the prep.

A 90-minute DP drill block

If DP still feels slippery:

1. 20 min — Climbing Stairs plus House Robber. Write both from scratch. For each, say the minimal state out loud before touching the keyboard.
2. 25 min — LIS, both the O(n²) DP version and the O(n log n) patience-sort version. Say why the state is the same and only the transition changes.
3. 20 min — Coin Change (fewest coins to reach amount). This is where the partition model bites — the state is amount, the transitions are - coin[j].
4. 15 min — Edit Distance between two strings. The state is (i, j) — positions in both strings. This is the same DP that runs inside git diff.
5. 10 min — Do one problem you have not seen before. Name the state in English before any code.

Skip the "top-50 DP problems" drills. Derive the state, state the trade-off, name the runtime. That is the whole round.

For the adjacent pattern on a graph surface, pair this with Graph Interview Questions.