Dynamic Programming

Dynamic programming solves problems with overlapping subproblems and optimal substructure by caching subproblem results.

1. The idea

Dynamic programming (DP) applies when a problem has overlapping subproblems (the same smaller inputs recur many times in a naive recursive solution) and optimal substructure (the optimal solution can be built from optimal solutions to subproblems). Caching subproblem results — memoization (top-down) or tabulation (bottom-up) — avoids recomputation.

The core of a DP solution is a recurrence relation, often called a Bellman-style recurrence, expressing the answer to a state in terms of answers to smaller/simpler states, plus a choice at the current step: $V (s) = max_{a} {r (s, a) + V (s^{'})}$ for some transition.

Recognizing DP means noticing that a brute-force recursive solution recomputes the same subproblem many times — turning exponential time into polynomial time by storing each subproblem's answer once.

2. Why it matters

DP problems are a staple of quant-dev interviews (and also appear in expected-value/optimal-stopping probability questions), testing whether you can find the right recursive decomposition.

3. Core mathematics

Generic DP recurrence

V (s) = a \in A (s) max {r (s, a) + V (next (s, a))}

Bellman-style; sum/min variants also common

Fibonacci with memoization

F (n) = F (n - 1) + F (n - 2), F (0) = 0, F (1) = 1

Naive recursion is O(2^n); memoized DP is O(n)

Time complexity

O (number of states \times work per state)

4. How to recognize it

Think of this when…

Naive recursive solution recomputes the same subproblem repeatedly
Problem asks for an optimal value (max/min/count) built from smaller instances of itself
Phrases like 'number of ways to...' or 'minimum cost to reach...'

5. Worked example

Worked example

Find the minimum number of coin denominations {1, 3, 4} needed to make change for 6, using DP.

1
Define dp[x] = minimum coins to make amount x, with dp[0]=0.
$d p [x] = c \in {1, 3, 4}, c \leq x min {d p [x - c] + 1}$
2
Build up: dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1, dp[5]=dp[1]+1=2 (using 4+1) or dp[2]+1=3 (using 3+... ) — take min = 2.
$d p [5] = min (d p [4] + 1, d p [2] + 1) = min (2, 3) = 2$
3
dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3,2,3) = 2, using two 3-coins.
$d p [6] = 2$
Answer: Minimum 2 coins (e.g. 3+3) to make change for 6, computed bottom-up in O(amount × number of denominations) time.

6. Common mistakes

Writing the naive exponential recursion without memoizing, missing the overlapping-subproblems structure
Defining the DP state incompletely, so it doesn't capture all information needed for correct transitions
Off-by-one errors in base cases (e.g. dp[0]) that cascade through the whole table

7. Quick check

Dynamic programming applies when a problem has:

Memoized Fibonacci computation runs in:

8. Practice

1 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Dynamic Programming / Continuation Value

Create a free account to save lesson progress.