Dynamic programming, and why it is the same as an EV recursion

Dynamic programming is recursion with the repeated work removed. The hard part is never the code — it is choosing the state. And once you see that an expected-value recursion is a dynamic programme over the same state space, half the probability questions in a trading interview become coding questions you already know how to do.

Proposition 6.1

The four questions

Every dynamic programme answers the same four questions, and answering them aloud in order is most of the interview. What is the state? What is the transition? What are the base cases? In what order can the states be evaluated so that each one’s dependencies are already computed?

Holds when

If the state is right, the transition is usually one line.
If you cannot find an ordering, the problem may need memoisation on a graph rather than a table — or it may have a cycle, in which case it is a linear system, not a DP.

Aspect	Memoisation (top-down)	Tabulation (bottom-up)
Written as	The natural recursion plus a cache	Loops filling an array
Visits	Only reachable states	Every state in the table
Risk	Stack depth on deep recursions	Computing states you never needed
Space	Hard to reduce below the full state space	Often reducible to one or two rows
Best when	The state space is sparse or awkward to order	The state space is dense and the order is obvious

Table 6.2 · Memoisation against tabulation.

from functools import cache

def climb_memo(n: int) -> int:
    """Ways to climb n stairs taking 1 or 2 at a time."""
    @cache
    def f(k: int) -> int:
        if k < 0:
            return 0
        if k == 0:
            return 1
        return f(k - 1) + f(k - 2)
    return f(n)

def climb_table(n: int) -> int:
    prev, cur = 1, 1          # f(0), f(1)
    for _ in range(2, n + 1):
        prev, cur = cur, cur + prev
    return cur                 # O(n) time, O(1) space

Listing 6.3 · Both forms, one problem. The tabulated version drops to constant space because the transition looks back only two states. Spotting that reduction is a standard follow-up. Time O(n) · Space O(n) memoised, O(1) tabulated.

Figure 6.4 · A recursion is a graph of reusable results. Each f(n) needs the two earlier states. The arrows point from a prerequisite to the result that uses it. A naive recursive call tree visits f(2) more than once; a table or cache computes this graph one node at a time.

Figure 6.5 · What memoisation is worth, on the fortieth Fibonacci number. The naive tree recomputes the same subproblems until the numbers stop being writable; the cache turns it into one pass. It is the same move as writing an expected-value recursion in terms of states you have already solved — dynamic programming and backward induction are one idea.

Dynamic programming, and why it is the same as an EV recursion

After this lesson you should be able to

The four questions

The rest of this lesson is in Premium