Dive C4.11.2 · part 2 of 3

Tabulation & bottom-up

Turn the recursion into a loop, and fill an array from the base case up. The target reads off cells already computed.

Bottom-up dynamic programming rewrites the recursion as a loop that fills a table from the smallest subproblem to the largest, so the final answer reads off cells already in place. It is eager — every cell is filled whether the answer needs it or not — usually with better constant factors and no deep stack. The worked problem is the change-making problem: the fewest modules (worth 1, 3, or 4 credits) summing to a target exactly. The answer for a total is 1 + min over worths w of dp[c-w], with dp[0] = 0 — optimal substructure. In F# the table is an Array, filled with a for loop or Array.fold; a two-dimensional recurrence uses Array2D. Where greedy strands a remainder, the table is optimal. Every value below was produced by dotnet fsi.

Fill from zero up Module hub

C4.11.2 · part 1

Fill an array, smallest first

Cell dp[c] is the fewest modules summing to c credits. It is one more than the best answer for c minus a module's worth, over the worths that fit. Each cell uses only smaller cells, so a single left-to-right pass fills the whole array. In F# the array is mutated in place inside the loop — the contained mutation of an algorithm, with an immutable result handed back.

// fewest modules (worth 1, 3, 4) to reach `target` credits, bottom-up
let fewest target =
    let worths = [1; 3; 4]
    let dp = Array.create (target + 1) System.Int32.MaxValue
    dp[0] <- 0                                  // base case: zero credits, zero modules
    for c in 1 .. target do
        for w in worths do
            if w <= c && dp[c - w] <> System.Int32.MaxValue then
                dp[c] <- min dp[c] (dp[c - w] + 1)  // 1 + a smaller, filled cell
    dp[target]
// val fewest: target: int -> int

fewest 6    // val it: int = 2   — two threes
fewest 11   // val it: int = 3   — 4 + 4 + 3

dp[c]: the fewest modules summing to c credits; the table cell. Built from dp[c-w] for each worth w that fits.
Array.create: allocates the table filled with a sentinel (Int32.MaxValue = "no solution yet"); the indexer dp[c] is O(1).
optimal substructure: an optimal answer for c is one module plus an optimal answer for a smaller total — the property that lets the table read off smaller cells.
the contained mutation: the array is mutated inside the loop, but the function returns a single value; the imperative shell is local to one algorithm.

Fill from zero up

Pick a target and watch the array fill from zero. The target cell is built from one smaller cell — drawn by the arc — and the readout names whether the grabby choice (take the biggest module that fits) matches the table or loses to it. Every number is the real value fewest computes.

Target credits · select one · modules worth 1, 3, 4

target: 6 credits

fewest modules: 2 modules

Every cell is solved once, smallest first, and the target reads straight off the array. Because each cell weighs all module choices, the table never gets trapped by a grabby first move.

C4.11.2 · part 2

Array.fold, and why greedy can lose

When the recurrence depends on a fixed window of earlier cells — Fibonacci-style — a fold expresses the same fill without the mutable array, carrying the running answers forward. The Fibonacci pacing count from the hub, written with Array.fold over a range, gives ways 10 = 89 and ways 20 = 10946, both verified in dotnet fsi.

The grabby alternative — take the biggest module that fits and repeat — is not always optimal. For a target of six it takes four, then two ones: three modules, because the leading four strands a remainder of two that only ones can fill. The table does better: two threes, two modules. The difference is that the grabby choice commits to a locally largest step, while dp[c] compares every module worth and keeps the best, so a worse-looking step that sets up a better finish is never ruled out.

// the same recurrence as a fold over 3..n, carrying a Map of running answers
let ways n =
    [3 .. n]
    |> List.fold (fun (t: Map<int, int>) i ->
        Map.add i (t[i - 1] + t[i - 2]) t) (Map [1, 1; 2, 2])
    |> fun t -> t[n]
// val ways: n: int -> int

ways 10   // val it: int = 89
ways 20   // val it: int = 10946

greedy

Largest module first — can strand a remainder and lose.

a bottom-up table

Every total solved from zero up, weighing all worths; the target is optimal.

C4.11.2 · part 3

When the table is two-dimensional

Some recurrences are indexed by two things at once — two strings, a capacity and an item, a row and a column. F# fills those with Array2D, the runtime's rectangular array, indexed d[i, j]. The next dive uses it for edit distance — the textbook two-dimensional DP — before the chapter's payoff. Tabulation suits a dense table where the answer genuinely needs the smaller cells, so computing them all wastes nothing, and the array index is O(1) with no recursion stack.

Tabulation is the same solve-each-once as memoisation, run eagerly from the base case up rather than lazily from the target down; here that trades the lookups for a flat pass over an array. The Array cost model is C4.01's; the choice of array versus map is C4.04's.

EchoMQ in F# — the delay curve is a tabulated array

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 computes a retry delay with EchoMQ.Backoff.delayMs policy attempts. Evaluated over attempts 1..N, it is itself a tabulated curve: build an array of the delay at each attempt and the whole retry schedule is a value, computed without a server. The Exponential case climbs by doubling, then holds at the cap.

echo_fs/EchoMQ/Backoff.fs · the curve as an array

// the retry schedule as a bottom-up array of delays, one per attempt
let curve policy n =
    [| for attempts in 1 .. n -> Backoff.delayMs policy attempts |]

let p = Backoff.Exponential(100, 10000)
curve p 8
// val it: int[] = [|100; 200; 400; 800; 1600; 3200; 6400; 10000|]

The curve climbs 100, 200, 400, 800, 1600, 3200, 6400 ms — each base · 2^(n-1) — then holds at the 10000 ms cap. Verified against dotnet fsi and against the policy's tests (delayMs p 1 = 100, delayMs p 3 = 400, delayMs p 20 = 10000 in EchoMQ.Tests/BackoffTests.fs).

The F# EchoMQ computes the curve today — built and tested. The Valkey transport EchoMQ.Connector lands next; the bus takes the literal delay and never computes a curve, so the table is the host's to fill.

A delay curve is a one-dimensional DP table the bus never has to keep: the host fills it from the recurrence and hands the wire a single literal. The next dive plots that table from its recurrence.

Where this leads

That is solve-each-once from the bottom up: a loop that fills an array, eager and stack-free. The last dive in this module takes the same machinery to the chapter's payoff — edit distance as a two-dimensional Array2D, then the EchoMQ backoff recurrence plotted from its definition.

↑ C4.11 · Dynamic programming ← C4.11.1 · Memoization C4.11.3 · Backoff as DP →

References

Sources

Microsoft — F# documentation — arrays, loops, and the change-making style of DP.
FSharp.Core API reference — the Array module, Array.fold, and Array2D.
Microsoft — .NET documentation — the array cost model on the CLR.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — F4.11.2 · Tabulation — the E4 sibling, the same table filled in Elixir.
C4.11 — Dynamic programming — the module hub.
C4.01 — Lists, recursion & complexity — arrays and the cost model on .NET.
C4 — Algorithms & Data Structures — the chapter.