Dynamic Programming: From Recursion to Table

Dynamic programming has a fearsome reputation and a mundane reality: it's recursion where you write answers down instead of recomputing them. If you can state a problem's answer in terms of smaller versions of itself, you can DP it.

The idea in one example

Naive recursive Fibonacci recomputes the same values exponentially many times ($O(\phi^n)$ calls). Two fixes:

• Memoization (top-down): keep the recursion, cache results in a dict. Each subproblem computed once: $O(n)$.
• Tabulation (bottom-up): fill an array from the base cases upward: f[i] = f[i-1] + f[i-2]. Same complexity, no recursion depth issues, and often you only need the last two values — $O(1)$ space.

DP applies when a problem has overlapping subproblems (the same smaller questions recur) and optimal substructure (the best answer builds from best sub-answers). The whole craft is defining the state — what a subproblem needs to remember.

The patterns that cover the interviews

1. Linear sequence. Climbing stairs (1 or 2 steps: ways = Fibonacci), house robber (take or skip: dp[i] = max(dp[i-1], dp[i-2] + v[i])). State: position, maybe one flag.

2. Running best — Kadane. Maximum-sum contiguous subarray in one pass: best_ending_here = max(x, best_ending_here + x). And its famous finance skin: best time to buy and sell a stock once — track the running minimum price and the best price − min_so_far. $O(n)$, two variables, asked constantly:

lo, best = float("inf"), 0
for p in prices:
    lo = min(lo, p)
    best = max(best, p - lo)

3. Knapsack / coin change. Budget-constrained choice: dp[amount] = fewest coins (or max value) using items considered so far. State: remaining capacity (× item index). Portfolio-construction toy questions are knapsacks wearing suits.

4. Two sequences. Edit distance, longest common subsequence: dp[i][j] compares prefixes. $O(mn)$ — the workhorse behind diff tools and sequence alignment; in interviews, recognizing the 2-D table shape is most of the battle.

The method, explicitly

1. Define the state in words: "dp[i] = the best P&L achievable using the first i prices." Undefined states cause every DP failure.
2. Write the recurrence — how does state $i$ follow from earlier states?
3. Base cases, then order of evaluation (or memoize and let recursion order itself).
4. Complexity = number of states × work per state. Say it unprompted.
5. Space-optimize if only a few previous rows are used.

Where DP touches quant work

Option pricing by backward induction on a binomial tree is textbook DP — the state is (time, node), the recurrence is the discounted expectation, base cases are terminal payoffs. American options add max(exercise, continue) — exactly the take-or-skip pattern. Optimal execution (spread a big order over the day) and optimal stopping problems have the same skeleton. Saying "this is the same backward induction as the binomial model" in a coding interview at a trading firm is a cross-disciplinary flex that lands.

The interview version

"Best time to buy and sell with at most two transactions?" — extend the state: dp[k][i] = best with $k$ transactions by day $i$; or the elegant four-variable scan (best after first buy/sell/second buy/sell). The escalation pattern — solve the simple version, then grow the state — is how every DP interview proceeds. Master the state-definition habit and the rest is bookkeeping.