Phase 5 — Dynamic Programming (Basic → Extreme)

Target level: Medium → Very Hard Expected duration: 4 weeks (12-week track) / 5 weeks (6-month track) / 6 weeks (12-month track) Weekly cadence: ~6 DP topics per week + 30–60 problems applying them under the framework

Why Dynamic Programming Is The Single Hardest Pattern Family In Coding Interviews

Phase 4 taught you that one-in-three Medium-Hard interview problems is a graph problem in disguise. The other big share is dynamic programming. DP shows up in roughly one in four Medium-Hard rounds at top-tier companies, and the share rises further in staff/principal and quant interviews where exact-counting and optimization questions dominate. More importantly, DP is the topic where the gap between candidates who have a framework and those who don’t is widest. A candidate without a DP framework freezes on dp[i][j] = ?; a candidate with one writes the recurrence in 90 seconds and spends the remaining time on edge cases.

The empirical claim that drives this entire phase:

The hard part of DP is not the code. The hard part is deriving the state. Almost every wrong DP solution is wrong because the state is wrong — too small to capture all the information needed, or so large that the table doesn’t fit in memory or time. Once the state is right, the transition writes itself, the base cases follow from the state, and the code is mechanical.

DP is also the topic where candidates most often memorize problems instead of internalizing the technique, and it is the topic where memorization fails most spectacularly. There are perhaps 60 named DP problems on LeetCode that everyone has seen; an interviewer who wants to filter out the memorizers asks the 61st. The solution, then, is not to drill 60 problems — it is to drill the derivation process until you can derive any DP from the recursive formulation.

This phase is built around one teaching device that we will use on every single problem from start to finish: the brute → memo → tabulated → space-optimized progression. Every problem you solve in this phase will be solved four times in succession:

Brute force — usually exponential recursion that explores every choice.
Memoized — the same recursion plus a cache, top-down DP, O(states × transition) time.
Tabulated — bottom-up loop in topological order on the state DAG, O(states × transition) time, no recursion stack.
Space-optimized — a rolling-array transformation that keeps only the previous one or two layers and reduces space from O(N · M) to O(M) or O(1).

By the end of this phase, you will execute this progression unconsciously. When an interviewer asks “can you reduce the space?”, you will already have written the tabulated version with the rolling array in mind. When the interviewer asks “what’s the recurrence?”, you will already have derived it from the brute-force recursion in the first 90 seconds of the problem. The four-stage progression is the single most valuable interview-time discipline taught in this entire curriculum, because it converts an open-ended “design a DP” question into a deterministic four-step recipe.

After this phase, you can solve canonical Hard DP problems on first attempt: edit distance in 25 minutes with full progression, longest increasing subsequence at both O(N²) and O(N log N), partition equal subset sum, coin change (count and minimum), burst balloons (interval DP), house robber III (tree DP), and shortest path visiting all nodes (bitmask DP). You will also become visibly stronger in mock interviews because you will reach for dp[i][j] notation on the whiteboard within 90 seconds and articulate the state definition out loud before writing any code.

What You Will Be Able To Do After This Phase

Recognize that a problem is a DP problem within 2 minutes, even when the words “DP” or “memoize” never appear in the statement.
Derive the state from a recursive brute force in <3 minutes by identifying the parameters that change across recursive calls.
Write the transition as a closed-form max/min/sum over a small set of choices, with clear correctness justification.
Identify base cases as the recursive function’s return statements at the smallest input.
Write the tabulated version by inverting the recursion into a loop with the right evaluation order on the state DAG.
Apply the rolling-array trick to reduce O(N · M) space to O(M) or O(1) when the recurrence depends only on the previous row(s).
Distinguish 0/1 knapsack from unbounded knapsack by a single change in the inner-loop direction.
Recognize when a “subset” or “partition” problem reduces to subset sum with target total / 2.
Implement LIS at both O(N²) (canonical DP) and O(N log N) (patience sorting + binary search) and explain the equivalence.
Implement edit distance with all four variants (brute, memo, tabulated, O(M)-space) in <25 minutes.
Implement tree DP via post-order recursion, returning multi-tuple state (e.g., “best with root included” and “best with root excluded”).
Implement interval DP with the canonical for length, for left, right = left + length - 1 loop structure.
Implement bitmask DP with state (mask, last) for TSP-style problems and (mask) alone for set-cover-style problems.
Articulate the correctness argument for every DP you write: state definition, transition justification, evaluation order, base case.
Spot the standard DP bugs unprompted: wrong base case, wrong evaluation order, off-by-one in indices, missed edge case at empty input.

How To Read This Phase

Read this README in two passes. Pass 1: linear, end-to-end, building a mental map of which DP variant solves which problem signal. Do this in one sitting. Pass 2: as you work the labs, refer back to specific topic entries to clarify state-design choices and pitfalls.

Each topic entry has a fixed shape:

When To Use — the problem signal that should fire this DP variant in <2 minutes.
State Design — what the state is, why these are the right parameters, why no fewer suffice.
Transition — the recurrence in closed form.
Complexity — time and space, and what space optimization is possible.
Common Pitfalls — the bugs that consume the most interview minutes for this DP variant specifically.
Classic Problems — 3–5 representative LeetCode problems where this DP is the intended solution.

The phase ends with a DP-Recognition Cheat Sheet (problem signals → DP variant), a Common-Bug Catalog, a Mastery Checklist, and Exit Criteria.

The DP Framework

Before any topic, internalize this framework. Use it on every DP problem.

1. State Definition

The state is the smallest set of parameters that uniquely determines the answer to a subproblem. Write it down explicitly:

dp[i] = the answer to the subproblem ending at / using up to / for prefix-of-length / etc., parameter i.

Sentences that begin “let dp[i] be” are the most valuable two seconds of the entire problem. If you can’t finish the sentence, you don’t have a state — you have a vague hope.

The state must be sufficient (encodes everything the future needs to know) and necessary (every parameter actually changes the answer). A common bug is a state that’s sufficient but not necessary — e.g., tracking both index and remaining-budget when budget is determined by index. Another is necessary but not sufficient — e.g., tracking only the index when the choice depends on what was picked earlier.

A useful test: two equal states must produce equal answers. If two different histories arrive at the same state but have different optimal continuations, the state is missing a dimension.

2. Transition Function

The transition expresses dp[state] as a function of dp[smaller_state] for one or more smaller states. It is the recurrence. For optimization problems, it is min or max over a small set of choices; for counting problems, it is a sum.

The transition has three parts:

Choices — the discrete set of moves at this state (include item or skip; pick this character or that one; rob this house or skip).
Cost / value — the contribution of each choice (the item’s weight, the operation’s cost, the gain from picking).
Aggregation — min / max / sum / OR over the choices.

Write the transition as:

dp[state] = aggregate over choice c in C(state): contribution(c) + dp[state - effect(c)]

Always keep C(state) finite and small — typically O(1), O(K), or O(N). Transitions that aren’t O(small) usually indicate a missing state dimension.

3. Base Cases

The base cases are the values of dp at the smallest (recursion-stopping) states. They are not optional; a missing or wrong base case is the single most common DP bug.

Identify base cases by writing the recursion first and looking at the return-statements:

def f(i):
    if i == 0: return 0  # ← THIS is the base case
    return f(i-1) + something

For 2D DP, the base cases are typically the entire first row and first column — set them explicitly before the main loop. For 3D DP and beyond, they’re a hyper-plane of dimension one less than the state.

A subtle base case bug: two different recursive paths reach the same base case but expect different return values. Usually this means the state is wrong (missing a dimension) and the base case has to “remember” which path it came from — impossible.

4. Evaluation Order

DP states form a DAG: state A points to state B iff dp[B] appears in the recurrence for dp[A]. To compute dp[A] we must have already computed dp[B]. The evaluation order is a topological order of this DAG.

For 1D DP indexed by i, the order is usually i = 0, 1, 2, …, N (increasing) or i = N, N-1, …, 0 (decreasing) — depending on whether your transition looks “back” or “forward”. Both work; pick one consistently.

For 2D DP indexed by (i, j), the order is usually row-major (for i: for j:) or column-major. The right one is the one that fills dp[i-1][j] and dp[i][j-1] before dp[i][j].

For interval DP indexed by (left, right), the order is by interval length ascending: for length in 1..N: for left, right = left + length - 1. This guarantees all sub-intervals are filled before the enclosing interval.

For tree DP, the order is post-order DFS: children are filled before the parent.

For bitmask DP, the order is by popcount ascending or by mask value ascending (since a sub-mask of m is < m).

5. Space Optimization (The Rolling-Array Technique)

If dp[i][j] depends only on dp[i-1][*] and dp[i][j-1], then once row i is computed we don’t need any earlier row. Keep only the current and previous row — O(N · M) becomes O(M).

If dp[i][j] depends only on dp[i-1][j] and dp[i-1][j-1] (no same-row dependency), you can collapse to a single row using right-to-left iteration in j — O(M) space.

If dp[i][j] depends on more rows (e.g., dp[i-2]), keep that many rows.

The rolling-array transformation is mechanical once the tabulated version is written. The interviewer often asks for it: “can you reduce the space?” Practice the transformation on every lab so it becomes reflex.

6. The Brute → Memo → Tabulated → Space-Optimized Progression

Apply this on every problem in this phase. It is the mandatory teaching device of this phase.

Brute force: exponential recursion that tries every choice. Often O(2^N) or O(N!). Don’t skip writing this — it is the direct source of your state and transition.
Memoized: same recursion + a cache (@lru_cache in Python, a HashMap in Java, an array in C++). Time becomes O(states × transition); space includes the recursion stack.
Tabulated: replace recursion with a loop in topological order on the state DAG. Same time complexity, but no recursion overhead, and the loop structure makes the dependency pattern explicit.
Space-optimized: roll the table down to O(M) or O(1) by exploiting the recurrence’s locality.

Each stage is a strictly smaller change from the previous: brute → memo is “add a cache”, memo → tabulated is “invert the call graph”, tabulated → space-optimized is “drop dimensions you don’t reuse”. This is deterministic engineering, not invention.

Signal in problem statement	Likely DP variant
“Count number of ways”	Counting DP — sum over choices
“Maximum / minimum cost” with sequential choices	Optimization DP
“Pick subset with property P” / “partition”	Subset / knapsack
“Longest / shortest subsequence”	LIS / LCS family
“Edit / transform A into B”	Edit distance family
“Each item used at most once”	0/1 knapsack
“Each item can be reused”	Unbounded knapsack
“Substring / subarray / contiguous”	1D DP (often Kadane-like)
“Subsequence (non-contiguous)”	LCS / LIS family
“Palindromic”	Interval DP, expand-around-center, or LCS(s, rev(s))
“Match a pattern with `*` / `.`”	Regex / wildcard DP
“Tree” + “subtree answer aggregates”	Tree DP, post-order
“N ≤ 20” + “visit all” / “subset”	Bitmask DP
“N ≤ 100” + “split into intervals” / “merge intervals”	Interval DP, length-ascending
“Two-player game, both optimal”	Game DP, perspective-flip
“Probability” / “expected” + “random walk / dice”	Probability/EV DP
“Number of digits ≤ 18, range [L, R]”	Digit DP
“Acyclic graph + longest/count paths”	DP on DAG
“Climbing / hopping with steps {a, b, c}”	1D DP, Fibonacci-like
“Decide YES/NO with budget K”	Reachability DP, often boolean knapsack

LeetCode Interview — Extreme Coding