Dynamic Programming Basics

Dynamic programming (DP) sounds intimidating and is really just one honest idea: if solving a big problem forces you to solve the same smaller problems over and over, solve each small problem once, write the answer down, and look it up next time. That's it. The name is historical and unhelpful; think of it as "careful recursion with a notebook."

The tell that DP applies is a recursion that keeps revisiting the same inputs. Compute Fibonacci naively — fib(n) = fib(n-1) + fib(n-2) — and fib(5) calls fib(3) twice, fib(2) three times, and so on. The call tree has about $2^n$ nodes, so it is exponential. But there are only $n$ distinct values it ever needs. Remember each one the first time you compute it, and the work drops to $O(n)$.

The two ingredients

DP works only when a problem has both of these:

• Optimal substructure — the best answer to the whole is built from the best answers to its parts.
• Overlapping subproblems — those parts recur, so caching pays off. (If subproblems never repeat, plain divide-and-conquer is enough; there is nothing to cache.)

Given those, you write a recurrence: a formula for the answer to a state in terms of smaller states, plus base cases. Everything else is bookkeeping.

Worked example: fewest coins to make change

You have coin denominations {1, 3, 4} and want to make the amount 6 with as few coins as possible. Let dp[a] be the minimum number of coins that sum to a. The recurrence is:

$$dp[a] = 1 + \min_{c \,\le\, a}\; dp[a - c], \qquad dp[0] = 0,$$

which reads: to make amount $a$, try using one coin $c$, then optimally make the remainder $a - c$; take the cheapest choice over all coins. Filling the table from 0 up to 6:

Amount a	0	1	2	3	4	5	6
dp[a]	0	1	2	1	1	2	2
best move	—	+1	+1+1	+3	+4	+4+1	+3+3

So 6 needs just 2 coins (3 + 3). Note how dp[5] reused dp[4] and dp[6] reused dp[3] — each cell was computed once and read by later cells. That reuse is the entire savings.

def min_coins(coins, amount):
    dp = [0] + [float("inf")] * amount     # dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount]

The complexity is amount × len(coins), i.e. $O(nk)$ — polynomial, versus the exponential naive recursion that would re-derive every remainder from scratch.

Where it shows up in quant-dev interviews

DP is one of the most-asked interview families, and it is genuinely load-bearing on a quant desk. Climbing stairs, longest common subsequence, the knapsack, edit distance, and maximum-subarray are the standard warm-ups. The reason firms lean on it: the binomial option-pricing lattice is textbook DP — the value at each node is built from the two child nodes one step later, filled backward from expiry (Binomial Option Pricing). Optimal execution and inventory schedules are solved by Bellman's equation, the same backward recursion. If you can frame a problem as "value of a state = best immediate choice + value of the resulting state," you are doing the same thing quants do to price and to trade.

The habit to build: spot the repeated subproblems, name the state, write the recurrence, decide the fill order, and only then code. Related patterns lean on the same reuse instinct — see Prefix Sums for the one-dimensional case and Monotonic Stack for a different way to avoid re-scanning.