Module C4.11

Dynamic programming & advanced problems

Solve each subproblem once, store it, reuse it — in F#, the store is one of this chapter's maps or an array.

Dynamic programming is the move for a problem that breaks into overlapping subproblems with optimal substructure: an optimal answer is built from optimal answers to smaller ones, and those smaller ones recur. Solve each once and store it, and exponential work becomes work proportional to the number of distinct subproblems. Two styles do this — memoisation caches a recursion top-down, tabulation fills a table bottom-up. This module reflects the Elixir course's E4.11, re-derived in F#: the cache is a Map threaded through a recursion or a mutable Dictionary; the table is an Array (or Array2D for a two-dimensional DP). It lands on a recurrence the bus already computes — EchoMQ.Backoff.

The three dives Back to C4 · Algorithms

The cost of recomputing

A learner works through a track of n lessons, taking one or two per session. The number of distinct pacings follows ways(n) = ways(n-1) + ways(n-2) — the same overlapping recurrence as Fibonacci. Computed naively it re-derives the lower terms over and over; computed with a store it touches each once. Pick a length to compare the work. Every count below is the real value, the same dotnet fsi produces.

Track length · select one

naive calls: 9

stored subproblems: 5

The answer is the same either way; the cost is not. Naive recursion pays for every repeat of a subproblem, and the repeats grow exponentially. Solving each subproblem once turns that into one evaluation per lesson.

Two styles, one idea

The two styles are the same idea from opposite ends. Memoisation keeps the natural recursion and adds a store, so it is lazy — it only ever evaluates the subproblems the answer actually needs — at the cost of recursion depth and a lookup per call. Tabulation rewrites the recursion as a loop that fills a table from the smallest subproblem up, so it is eager and iterative, usually with better constant factors and no deep stack, at the cost of computing every cell whether the answer needs it or not.

In F# the store is concrete. Memoisation reaches for a mutable System.Collections.Generic.Dictionary (O(1) amortised) or an immutable Map threaded through the recursion (O(log n), referentially transparent). Tabulation reaches for an Array filled with a for loop or Array.fold — or an Array2D when the recurrence is two-dimensional. The same recurrence, written both ways, was verified in dotnet fsi.

F# — the same recurrence, both ways (verified in FSI)

// top-down: a recursion plus a Dictionary cache
let waysMemo () =
    let cache = Dictionary<int, int>()
    let rec go n =
        if n <= 2 then n
        else
            match cache.TryGetValue n with
            | true, v -> v
            | _ -> let v = go (n - 1) + go (n - 2) in cache[n] <- v; v
    go
// val waysMemo: unit -> (int -> int)

// bottom-up: fill an array from the base cases up
let waysTab n =
    let dp = Array.zeroCreate (max (n + 1) 3)
    dp[1] <- 1; dp[2] <- 2
    for i in 3 .. n do dp[i] <- dp[i - 1] + dp[i - 2]
    dp[n]
// val waysTab: n: int -> int
waysTab 10   // val it: int = 89
waysTab 20   // val it: int = 10946

overlapping subproblems

The same smaller answers, needed again and again, with an optimal answer built from optimal parts.

solve each once

Cache a recursion in a Dictionary/Map, or fill an Array; exponential work becomes one pass over the subproblems.

The three dives

Read them in order: the two styles, then a recurrence the bus already computes. Each stands on valid F# verified in dotnet fsi, beside its Elixir E4.11 sibling, and carries an EchoMQ in F# block grounded in the real echo_fs port.

live module hub built dive ready soon specified

C4.11.1 · top-down

Memoization & overlapping subproblems

Keep the recursion and add a store: a mutable Dictionary for O(1) lookup, or a Map threaded to stay pure. Lazy — only the subproblems the answer needs. A consumer can memoise its retry schedule so a repeated attempt-count never recomputes a delay.

C4.11.2 · bottom-up

Tabulation & bottom-up

Fill an Array from the base case up — the fewest modules to reach a credit target, where greedy can lose and the table cannot. Backoff.delayMs over attempts 1..N is itself a tabulated delay curve.

C4.11.3 · the payoff

Backoff as dynamic programming

Edit distance as the classic two-dimensional Array2D DP, then the direct hit: EchoMQ.Backoff is a pure recurrence base · 2^(n-1) clamped — the host computes the curve above the wire.

EchoMQ in F# — a recurrence above the wire

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

The chapter's bus is echo_fs, the F# port of echo/apps/echo_mq. Its retry-delay vocabulary, EchoMQ.Backoff, is exactly the shape this module teaches: a recurrence solved once per attempt count. The Exponential case is base · 2^(attempts-1) clamped to a ceiling, and the module's own documentation states the design — the wire takes a literal delay and never computes a curve, so the cadence is a value the caller can compute, table, and test without a server.

echo_fs/EchoMQ/Backoff.fs · the recurrence, verbatim

// `base * 2^(attempts-1)`, clamped to a ceiling — quoted from echo_fs
| Exponential (baseMs, capMs) ->
    let shift = attempts - 1
    if shift >= 62 then capMs
    else int (min (int64 baseMs * (1L <<< shift)) (int64 capMs))

Tabulate it over attempts 1..N and the whole retry schedule is a delay curve. For Exponential(100, 10000) the curve over 1..8 is [100; 200; 400; 800; 1600; 3200; 6400; 10000] — climbing, then holding at the cap.

The F# EchoMQ computes the backoff curve today — built and tested (EchoMQ.Tests/BackoffTests.fs). The Valkey transport EchoMQ.Connector lands next; when it does, the consumer still computes the curve host-side and the bus still takes the literal.

Dynamic programming's promise — solve the recurrence once, read the answer back — is the bus's design made concrete. The recurrence is the Exponential case; the table is the delay curve; the third dive plots it.

References

Sources

Microsoft — F# documentation — recursion, pattern matching, and the collection types.
FSharp.Core API reference — Map, Array, and Array2D, the stores DP uses.
Microsoft — .NET documentation — Dictionary<TKey,TValue> and the .NET cost model.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — F4.11 · Dynamic programming — the E4 sibling this module reflects, the same arc in Elixir.
C4.04 — Maps, sets & hashing — the immutable Map behind the cache.
C4 — Algorithms & Data Structures — the chapter this module sits in.
C1 — F# Language — recursion, pattern matching, and discriminated unions.
F# In Depth — the course home.