Dynamic Programming

Fibonacci Memo Table

Fill Fibonacci values once and reuse earlier cells. This is a small deterministic dynamic-programming example.

Example

Fill Fibonacci values once and reuse earlier cells.

highlighted = computed this step

Step 1 — Memo cell

Compute the highlighted combinatorics value.

n, inputs, value(0, (base), 0)\begin{array}{c|c}\text{n, inputs, value}&\hlmath{\text{(0, (base), 0)}}\end{array}

Step 2 — Memo cell

Compute the highlighted combinatorics value.

n, inputs, value(1, (base), 1)\begin{array}{c|c}\text{n, inputs, value}&\hlmath{\text{(1, (base), 1)}}\end{array}

Step 3 — Memo cell

Compute the highlighted combinatorics value.

n, inputs, value(2, (1, 1, 0, 0), 1)\begin{array}{c|c}\text{n, inputs, value}&\hlmath{\text{(2, (1, 1, 0, 0), 1)}}\end{array}

Step 4 — Memo cell

Compute the highlighted combinatorics value.

n, inputs, value(3, (2, 1, 1, 1), 2)\begin{array}{c|c}\text{n, inputs, value}&\hlmath{\text{(3, (2, 1, 1, 1), 2)}}\end{array}

Step 5 — Memo cell

Compute the highlighted combinatorics value.

n, inputs, value(4, (3, 2, 2, 1), 3)\begin{array}{c|c}\text{n, inputs, value}&\hlmath{\text{(4, (3, 2, 2, 1), 3)}}\end{array}

Step 6 — Memo cell

Compute the highlighted combinatorics value.

n, inputs, value(5, (4, 3, 3, 2), 5)\begin{array}{c|c}\text{n, inputs, value}&\hlmath{\text{(5, (4, 3, 3, 2), 5)}}\end{array}

Step 7 — Memo cell

Compute the highlighted combinatorics value.

n, inputs, value(6, (5, 5, 4, 3), 8)\begin{array}{c|c}\text{n, inputs, value}&\hlmath{\text{(6, (5, 5, 4, 3), 8)}}\end{array}
combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.