From recursion to dynamic programming

Dynamic programming in a coding round rarely starts as dynamic programming. It starts as a recursion that is correct and far too slow, because it solves the same smaller problem again and again. The fix comes in two steps. First, memoise (also spelled memoize): keep the answer to each smaller problem the first time it is worked out, and look it up every time it is asked for again, so that each distinct problem costs one computation instead of thousands. Second, if you need to, tabulate: work the answers out in an order in which everything each one needs is already known, from the smallest problems up, and fill a table in a loop. The first form is called top-down and the second bottom-up, and both are dynamic programming.

This lesson takes one counting problem through every step, with the calls counted at each one: a brute force that lists every answer, a recursion that counts them, the same recursion with a cache, and a table, finished in five languages. Then it gives the rule that prices any such solution, the number of states times the work per state, and the two ways a Python cache trips people up.

When a recursion is a DP in disguise

Two properties make a recursive solution worth caching. It builds its answer from the answers to smaller problems of the same kind: the ways to finish a job from the ways to finish what is left of it, or the cheapest route from the cheapest routes out of the next stop. And those smaller problems repeat: different early choices lead to the same leftover problem. Textbooks call the two properties optimal substructure and overlapping subproblems. NIST’s Dictionary of Algorithms and Data Structures describes dynamic programming in the same terms, as caching the solutions of subproblems instead of computing them again, and memoisation as saving a computed answer for later reuse.

The statement of a problem usually gives the pattern away:

• It asks for a count, a best value or a yes-or-no answer: “how many ways”, “the fewest coins”, “the largest total”, “can the string be split”.
• The answer comes from choices made one after another, and each choice leaves a smaller version of the same problem: a shorter floor, a later position in a list, a smaller amount of money.
• The limits are too large for trying everything and small enough for a table: n up to 10⁵ or 10⁶ for one index, a few thousand for each of two.

Three things point elsewhere:

• The answer is the list of solutions itself, such as every subset or every arrangement. The output alone is exponential, so the method is backtracking, and no cache makes the output shorter.
• The smaller problems never repeat. Merge sort’s two halves share nothing, so caching them would only use memory. That is divide and conquer.
• What is left depends on the whole path so far, not on a few numbers, so a cache would need a key as large as the path. Often a better description of the leftover problem fixes this; the next lesson of this module is about choosing it.

The quickest test is to count. Run the recursion on a small input, record how often each set of arguments comes back, and look. The problem below shows what the numbers look like.

A problem solved in full: tiling a verandah

Some answers, which every version below prints or checks:

• n = 1 gives 1: one tile across.
• n = 2 gives 2: two tiles across, or two tiles along, one above the other.
• n = 3 gives 3, n = 4 gives 5 and n = 10 gives 89.
• n = 50 gives 365010934, which is the count 20,365,011,074 reduced modulo 1,000,000,007.
• n = 1,000,000 gives 534400663.

The brute force: list every layout

Start with the method of the backtracking lesson. The state is the floor; each step puts one tile on the first empty cell, column by column and the top cell before the bottom one; the choices are a tile across or a tile along; and the constraint is that both cells of the tile are on the floor and empty. Each layout prints as two rows of letters, one letter per tile, so a letter above itself is a tile across and a letter twice in a row is a tile along:

"""Every way to tile a 2 x n verandah with 1 x 2 tiles, listed by backtracking: choose, explore, unchoose."""

NAMES = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def layouts(n):
    """Every layout of a 2 x n floor as (top row, bottom row), one letter per tile, and the number of calls made."""
    found = []
    floor = [[None] * n, [None] * n]  # the state: which tile covers each cell so far (None: still empty)
    calls = 0

    def first_empty():
        for col in range(n):  # column by column, the top cell before the bottom one
            for row in (0, 1):
                if floor[row][col] is None:
                    return row, col
        return None

    def backtrack(placed):
        nonlocal calls
        calls += 1
        cell = first_empty()
        if cell is None:  # goal: every cell is covered, so record a copy of the layout
            found.append(("".join(floor[0]), "".join(floor[1])))
            return
        row, col = cell
        name = NAMES[placed % len(NAMES)]
        # Choices: a tile across the verandah (this cell and the one below it), or a tile along it (this cell and
        # the next one in its row).
        for r, c in ((row + 1, col), (row, col + 1)):
            if r > 1 or c >= n or floor[r][c] is not None:  # constraint: both cells on the floor and empty
                continue
            floor[row][col] = floor[r][c] = name  # choose
            backtrack(placed + 1)  # explore
            floor[row][col] = floor[r][c] = None  # unchoose

    backtrack(0)
    return found, calls


for n in (1, 2, 3, 4):
    found, _ = layouts(n)
    print(f"n = {n}: {len(found)} layout{'' if len(found) == 1 else 's'}")
    print("   " + "   ".join(top for top, _ in found))
    print("   " + "   ".join(bottom for _, bottom in found))

print()
print(" n   layouts    calls")
for n in (5, 10, 15, 20):
    found, calls = layouts(n)
    print(f"{n:2}  {len(found):8,}  {calls:7,}")

n = 1: 1 layout
   A
   A
n = 2: 2 layouts
   AB   AA
   AB   BB
n = 3: 3 layouts
   ABC   ABB   AAC
   ABC   ACC   BBC
n = 4: 5 layouts
   ABCD   ABCC   ABBD   AACD   AACC
   ABCD   ABDD   ACCD   BBCD   BBDD

 n   layouts    calls
 5         8       27
10        89      320
15       987    3,569
20    10,946   39,601

The listing is the reference that every faster version below is checked against, because it is easy to believe. It is also hopeless at the stated size. Each extra column multiplies the number of layouts by about 1.6, from 89 at n = 10 to 10,946 at n = 20, and the search makes about 3.6 calls for each layout it finds. The counts are the Fibonacci numbers, which NIST’s dictionary gives as about φⁿ / √5, with φ = (1 + √5) / 2 ≈ 1.618. At n = 90 there are 4,660,046,610,375,530,309 layouts, more than any search could visit, and by that formula the count for n = 1,000,000 is a number about 209,000 digits long.

What to notice

Look at the first column of any layout. Its top cell is covered either by a tile across, which covers the cell below it too, or by a tile along. In the second case the cell below can only take a second tile along: a tile across would need the top cell, which is taken. So every layout begins in exactly one of two ways, and what is left after each is a shorter verandah, 2 × (n − 1) after a tile across and 2 × (n − 2) after two tiles along.

Count instead of listing

Counting needs none of the layouts themselves. The two ways to begin never give the same layout, because they put different tiles on the first top cell, and between them they give every layout, so the count for length n is the count for n − 1 plus the count for n − 2. The base cases are the shortest floors. A floor of length 1 takes one tile across: one layout. A floor of length 0 is already covered, which also counts as one layout, the one with no tiles, and with it the rule gives 1 + 1 = 2 for length 2, as the listing does.

Here is that recursion, with a counter that records how often each argument is asked for:

"""The layouts counted by a plain recursion, with every call counted: the same arguments come back again and again."""
from collections import Counter

calls = Counter()  # argument -> how many times tilings() was called with it


def tilings(n):
    """The number of layouts of a 2 x n verandah."""
    calls[n] += 1
    if n <= 1:
        return 1  # length 0: one layout, with no tiles; length 1: one tile across
    # The first column takes one tile across (a floor of length n - 1 is left) or two tiles along (n - 2 is left).
    return tilings(n - 1) + tilings(n - 2)


print("tilings(10) =", tilings(10))
print("argument  " + " ".join(f"{k:>3}" for k in range(10, -1, -1)))
print("calls     " + " ".join(f"{calls[k]:>3}" for k in range(10, -1, -1)))

print()
print(" n     layouts        calls")
for n in (10, 20, 25, 30):
    calls.clear()
    count = tilings(n)
    print(f"{n:2}  {count:10,}  {calls.total():11,}")

tilings(10) = 89
argument   10   9   8   7   6   5   4   3   2   1   0
calls       1   1   2   3   5   8  13  21  34  55  34

 n     layouts        calls
10          89          177
20      10,946       21,891
25     121,393      242,785
30   1,346,269    2,692,537

The answers are right and the cost is not. For n = 10 the function is called 177 times to compute 89, and the second line shows why: it works out tilings(2) 34 times and tilings(1) 55 times, each time from scratch. Every call either returns 1 at a base case or adds up what two more calls return, so the answer is the number of calls that end at a base case. Each of the other calls makes exactly two calls, so there is one fewer of them than of the base-case calls, and the total is 2 × tilings(n) − 1: 2,692,537 calls for n = 30. Counting is no faster than listing; it only stores less. The 31 different arguments from 0 to 30 are asked for more than 2.6 million times between them, and that repetition is what a cache removes.

Memoise: work out each length once

The number of layouts for a given length never changes, so keep it. Python’s functools.cache does that in one line: it wraps the function with a dictionary keyed by the arguments, returns the stored answer when the same arguments come back, and otherwise runs the function and stores its result. The Python documentation describes it as a simple cache with no size limit that returns the same as lru_cache(maxsize=None); it was added in Python 3.9, so on older versions lru_cache(maxsize=None) does the same job.

"""The same recursion, memoised: each argument is worked out once, and every later call looks the answer up."""
from functools import cache


@cache
def tilings(n):
    """The number of layouts of a 2 x n verandah (the decorator remembers every answer by its argument)."""
    if n <= 1:
        return 1
    return tilings(n - 1) + tilings(n - 2)


print(f"tilings(30) = {tilings(30):,}")
print(tilings.cache_info())


def tilings_by_hand(n):
    """The same with a dictionary as the cache, and every call counted: what @cache does for you."""
    memo = {}  # length -> number of layouts, filled the first time each length is asked for
    calls = 0

    def count(k):
        nonlocal calls
        calls += 1
        if k <= 1:
            return 1
        if k not in memo:
            memo[k] = count(k - 1) + count(k - 2)
        return memo[k]

    return count(n), calls


print()
print(" n                    layouts  calls")
for n in (10, 30, 90):
    layouts, calls = tilings_by_hand(n)
    print(f"{n:2}  {layouts:25,}  {calls:5}")

tilings(30) = 1,346,269
CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)

 n                    layouts  calls
10                         89     19
30                  1,346,269     59
90  4,660,046,610,375,530,309    179

cache_info() reports what happened for n = 30: 31 misses, one for each length from 0 to 30, when the function body ran, and 28 hits, when a stored answer came back instead. That is 59 calls in place of 2,692,537. The second version does the same with a dictionary, which is what you write in a language without such a decorator, and its count of calls, 2n − 1, grows in a straight line: 179 calls for n = 90, whose answer has 19 digits. The logic of the recursion did not change at all, which is why memoising is the safest first step in an interview: you write the brute force, test it, and make it fast by adding one line or one dictionary.

Tabulate: fill the table from the shortest floor up

The memo still recurses. tilings(30) calls tilings(29), which calls tilings(28), and so on down to the base cases before any answer comes back, and only then are the answers worked out, from length 2 upwards. A table does that directly. Let ways[k] be the number of layouts of a 2 × k floor, set the base cases, then fill each entry from the two before it, in increasing k, so that both entries it reads are already filled:

"""The same answers bottom-up: a table filled from the shortest floor to the longest, then two variables instead."""


def tilings_table(n, show=False):
    """ways[k] is the number of layouts of a 2 x k verandah; every entry is filled after the two it reads."""
    ways = [0] * (n + 1)
    ways[0] = 1  # base case: the empty floor has one layout
    if n >= 1:
        ways[1] = 1  # base case: one tile across
    if show:
        print(" k  reads              values  ways[k]")
        print(" 0  base case                        1")
        print(" 1  base case                        1")
    for k in range(2, n + 1):
        ways[k] = ways[k - 1] + ways[k - 2]
        if show:
            values = f"{ways[k - 1]} + {ways[k - 2]}"
            print(f"{k:2}  ways[{k - 1}] + ways[{k - 2}]  {values:<6}  {ways[k]:>7}")
    return ways[n]


def tilings_two_variables(n):
    """Only the last two entries are ever read, so two variables replace the table."""
    before, last = 1, 1  # ways[k - 2] and ways[k - 1], starting at k = 2
    for _ in range(n - 1):
        before, last = last, before + last
    return last


tilings_table(6, show=True)
print()
for n in (1, 2, 30, 90):
    print(f"n = {n:2}: table {tilings_table(n):,}, two variables {tilings_two_variables(n):,}")
print("agree for n = 1 to 500:", all(tilings_table(n) == tilings_two_variables(n) for n in range(1, 501)))

 k  reads              values  ways[k]
 0  base case                        1
 1  base case                        1
 2  ways[1] + ways[0]  1 + 1         2
 3  ways[2] + ways[1]  2 + 1         3
 4  ways[3] + ways[2]  3 + 2         5
 5  ways[4] + ways[3]  5 + 3         8
 6  ways[5] + ways[4]  8 + 5        13

n =  1: table 1, two variables 1
n =  2: table 2, two variables 2
n = 30: table 1,346,269, two variables 1,346,269
n = 90: table 4,660,046,610,375,530,309, two variables 4,660,046,610,375,530,309
agree for n = 1 to 500: True

The dry run for n = 6 is the whole algorithm: each row reads two filled entries and writes one. Turning any memo into a table takes three decisions:

1. The table has one entry per state, where a state is one set of values of the arguments that change between calls. Here that is the length k, from 0 to n.
2. The base cases of the recursion become the first entries, ways[0] and ways[1].
3. The loop visits the states so that every state comes after the states it asks for. A call on k asks for k − 1 and k − 2, so k increases. In the wrong order the loop reads entries that are still 0, and no error says so.

Only the last two entries are ever read, so the second function replaces the table with two variables, before and last, and the check at the end shows that the two versions agree for every n up to 500. That takes the memory from O(n) to O(1); a later lesson of this module does the same for tables with two indices.

Why it is correct

Two facts make the table right. The recurrence counts every layout exactly once: a layout starts either with a tile across or with two tiles along, never with both, so adding the counts of the two shorter floors misses no layout and counts none twice. And the loop keeps an invariant: before the step for k, every entry from ways[0] to ways[k − 1] holds the number of layouts of its floor. The base cases make it true for k = 2. Each step writes ways[k] from two entries that are already right, so it stays true. When the loop ends, ways[n] is right. The lesson on dry runs and invariants argues loops the same way.

Up to a million columns: depth and size

The limits allow n up to 1,000,000 and ask for the answer modulo 1,000,000,007, and each of the two changes the code.

The depth comes first. The memo works its way down to a base case before it stores anything, so for n it needs about n calls open at once, each waiting for the one below it. CPython stops a recursion that goes deeper than sys.getrecursionlimit() with RecursionError, and the limit is 1,000 unless a program changes it:

"""How deep a memoised recursion can go in CPython with its default settings, and the table that has no depth."""
import sys
from functools import cache

MOD = 1_000_000_007


@cache
def tilings_memo(n):
    if n <= 1:
        return 1
    return (tilings_memo(n - 1) + tilings_memo(n - 2)) % MOD


def tilings_table(n):
    ways = [0] * (n + 1)
    ways[0] = ways[1] = 1
    for k in range(2, n + 1):
        ways[k] = (ways[k - 1] + ways[k - 2]) % MOD
    return ways[n]


print("recursion limit:", sys.getrecursionlimit())
for n in (900, 2_000):
    tilings_memo.cache_clear()
    try:
        print(f"memoised, n = {n:,}: {tilings_memo(n)}")
    except RecursionError as error:
        print(f"memoised, n = {n:,}: RecursionError: {error}")
for n in (900, 2_000, 1_000_000):
    print(f"table,    n = {n:,}: {tilings_table(n)}")

recursion limit: 1000
memoised, n = 900: 50619274
memoised, n = 2,000: RecursionError: maximum recursion depth exceeded
table,    n = 900: 50619274
table,    n = 2,000: 276439883
table,    n = 1,000,000: 534400663

The memo answers n = 900 and fails at n = 2,000, while the table, a loop, has no depth to run out of and fills a million entries. Raising the limit with sys.setrecursionlimit() is not a dependable way out: the documentation warns that a limit set too high can crash Python, and a function wrapped by functools.cache also uses the C stack, which the lesson on Python for interviews measures running out between 5,000 and 20,000 levels. For long inputs, use the table.

Then the size. Python’s integers have unlimited precision, so the exact count is always there to compute, but it is a long number:

"""Why the count is asked for modulo 1,000,000,007: the exact counts outgrow every fixed-size integer type."""
import sys

MOD = 1_000_000_007


def tilings_exact(n):
    before, last = 1, 1
    for _ in range(n - 1):
        before, last = last, before + last
    return last


def tilings_mod(n):
    before, last = 1, 1
    for _ in range(n - 1):
        before, last = last, (before + last) % MOD  # reduce after every addition: both stay below MOD
    return last


for n in (1_000, 10_000, 100_000):
    exact = tilings_exact(n)
    print(f"n = {n:>7,}: the exact count has {exact.bit_length():>6,} bits; modulo MOD it is {exact % MOD:>9}, "
          f"the same as tilings_mod: {exact % MOD == tilings_mod(n)}")

for name, largest in (("a JavaScript number holds exactly", 2**53 - 1), ("a signed 64-bit integer holds", 2**63 - 1)):
    n = next(n for n in range(1, 200) if tilings_exact(n) > largest)
    print(f"the first count above the largest integer {name}: n = {n}, {tilings_exact(n):,} layouts")

try:
    print(len(str(tilings_exact(100_000))))
except ValueError as error:
    print("str() of the exact count for n = 100,000: ValueError:", error)

bits = sys.int_info.bits_per_digit
print(f"every residue fits in one {bits}-bit CPython digit, because MOD < 2 ** {bits}:", MOD < 2**bits)

n =   1,000: the exact count has    694 bits; modulo MOD it is 107579939, the same as tilings_mod: True
n =  10,000: the exact count has  6,942 bits; modulo MOD it is  24223428, the same as tilings_mod: True
n = 100,000: the exact count has 69,424 bits; modulo MOD it is 967618232, the same as tilings_mod: True
the first count above the largest integer a JavaScript number holds exactly: n = 78, 14,472,334,024,676,221 layouts
the first count above the largest integer a signed 64-bit integer holds: n = 92, 12,200,160,415,121,876,738 layouts
str() of the exact count for n = 100,000: ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit
every residue fits in one 30-bit CPython digit, because MOD < 2 ** 30: True

The exact count grows by about 0.69 bits per column: 69,424 bits at n = 100,000, which is about 20,900 decimal digits. That is past the 4,300 digits that CPython converts to a decimal string by default, so str() raises ValueError, as the output shows; the documentation explains the limit as a guard against denial-of-service attacks and sys.set_int_max_str_digits() raises it. In other languages the trouble starts much sooner. The count for n = 78 is the first above the largest integer a JavaScript number holds exactly, 2⁵³ − 1, and the count for n = 92 is the first above the largest signed 64-bit integer, so an exact count in JavaScript, Java, C++ or Go is wrong long before n = 1,000,000.

Reducing modulo 1,000,000,007 after every addition fixes both problems at once. Every value stays below 1,000,000,007, which is below 2³⁰, so in CPython each one fits in a single 30-bit digit of the integer’s internal form, and in every other language it fits in an ordinary integer. The residues are the same as reducing the exact count once at the end, as the first three lines check, because a remainder taken after each addition gives the same result as one taken at the end. The exact loop is also slower, because its numbers keep getting longer:

"""The exact loop against the modular one, timed: the exact numbers get longer as the loop goes, so it slows down."""
import time

MOD = 1_000_000_007


def tilings_exact(n):
    before, last = 1, 1
    for _ in range(n - 1):
        before, last = last, before + last
    return last


def tilings_mod(n):
    before, last = 1, 1
    for _ in range(n - 1):
        before, last = last, (before + last) % MOD
    return last


def best_of_three(count, n):
    """The fastest of three runs, in milliseconds: other programs on the computer only ever make a run slower."""
    times = []
    for _ in range(3):
        start = time.perf_counter()
        count(n)
        times.append((time.perf_counter() - start) * 1000)
    return min(times)


for name, count, n in (("exact", tilings_exact, 10_000), ("exact", tilings_exact, 100_000),
                       ("modulo", tilings_mod, 100_000), ("modulo", tilings_mod, 1_000_000)):
    print(f"{name:>6}, n = {n:>9,}: {best_of_three(count, n):7.1f} ms")

 exact, n =    10,000:     1.9 ms
 exact, n =   100,000:   152.1 ms
modulo, n =   100,000:     6.4 ms
modulo, n = 1,000,000:    96.4 ms

Expect other numbers on your computer, and different ones each time you run it; what does not change is how each loop grows. The modular loop’s time grows about as fast as n does. The exact loop’s grows far faster: in the recorded run, ten times the columns made it about 80 times slower, because every addition near the end works on numbers tens of thousands of bits long.

The code in five languages

Here is the final version, a table filled bottom-up with a reduction after every addition. You can run the Python or the JavaScript version here in the page; the other three need a compiler, so the session below shows them built and run on the pinned toolchains.

"""Layouts of a 2 x n verandah tiled with 1 x 2 tiles, modulo 1,000,000,007, filled bottom-up."""
MOD = 1_000_000_007


def tilings(n):
    """The number of layouts of a 2 x n floor modulo MOD, for 1 <= n <= 1,000,000."""
    ways = [0] * (n + 1)  # ways[k]: the layouts of a 2 x k floor, modulo MOD
    ways[0] = ways[1] = 1  # the empty floor, and one tile across
    for k in range(2, n + 1):  # every entry after the two it reads
        ways[k] = (ways[k - 1] + ways[k - 2]) % MOD
    return ways[n]


for n in (1, 2, 3, 4, 10, 50, 1_000_000):
    print(f"tilings({n}) = {tilings(n)}")

tilings(1) = 1
tilings(2) = 2
tilings(3) = 3
tilings(4) = 5
tilings(10) = 89
tilings(50) = 365010934
tilings(1000000) = 534400663

// Layouts of a 2 x n verandah tiled with 1 x 2 tiles, modulo 1,000,000,007, filled bottom-up.
const MOD = 1_000_000_007;

// The number of layouts of a 2 x n floor modulo MOD, for 1 <= n <= 1,000,000.
function tilings(n) {
  const ways = new Array(n + 1).fill(0); // ways[k]: the layouts of a 2 x k floor, modulo MOD
  ways[0] = ways[1] = 1; // the empty floor, and one tile across
  for (let k = 2; k <= n; k++) {
    // Two residues add up to less than 2,000,000,014, far below 2 ** 53, so the sum is exact.
    ways[k] = (ways[k - 1] + ways[k - 2]) % MOD;
  }
  return ways[n];
}

for (const n of [1, 2, 3, 4, 10, 50, 1_000_000]) {
  console.log(`tilings(${n}) = ${tilings(n)}`);
}

tilings(1) = 1
tilings(2) = 2
tilings(3) = 3
tilings(4) = 5
tilings(10) = 89
tilings(50) = 365010934
tilings(1000000) = 534400663

// Layouts of a 2 x n verandah tiled with 1 x 2 tiles, modulo 1,000,000,007, filled bottom-up.
public class Tilings {
    static final int MOD = 1_000_000_007;

    // The number of layouts of a 2 x n floor modulo MOD, for 1 <= n <= 1,000,000.
    static int tilings(int n) {
        int[] ways = new int[n + 1]; // ways[k]: the layouts of a 2 x k floor, modulo MOD
        ways[0] = ways[1] = 1; // the empty floor, and one tile across
        for (int k = 2; k <= n; k++) {
            // Both residues are below MOD, so their sum is below 2,000,000,014: it fits in an int.
            ways[k] = (ways[k - 1] + ways[k - 2]) % MOD;
        }
        return ways[n];
    }

    public static void main(String[] args) {
        for (int n : new int[] {1, 2, 3, 4, 10, 50, 1_000_000}) {
            System.out.println("tilings(" + n + ") = " + tilings(n));
        }
    }
}

// Layouts of a 2 x n verandah tiled with 1 x 2 tiles, modulo 1,000,000,007, filled bottom-up.
#include <limits>
#include <print>
#include <vector>

constexpr int MOD = 1'000'000'007;
// Both residues are below MOD, so their sum is below 2,000,000,014: check that an int holds it.
static_assert(std::numeric_limits<int>::max() >= 2LL * (MOD - 1));

// The number of layouts of a 2 x n floor modulo MOD, for 1 <= n <= 1,000,000.
int tilings(int n) {
    std::vector<int> ways(n + 1);  // ways[k]: the layouts of a 2 x k floor, modulo MOD
    ways[0] = ways[1] = 1;         // the empty floor, and one tile across
    for (int k = 2; k <= n; k++) {
        ways[k] = (ways[k - 1] + ways[k - 2]) % MOD;
    }
    return ways[n];
}

int main() {
    for (int n : {1, 2, 3, 4, 10, 50, 1'000'000}) {
        std::println("tilings({}) = {}", n, tilings(n));
    }
}

// Layouts of a 2 x n verandah tiled with 1 x 2 tiles, modulo 1,000,000,007, filled bottom-up.
package main

import "fmt"

const MOD = 1_000_000_007

// tilings returns the number of layouts of a 2 x n floor modulo MOD, for 1 <= n <= 1,000,000.
func tilings(n int) int {
	ways := make([]int, n+1) // ways[k]: the layouts of a 2 x k floor, modulo MOD
	ways[0], ways[1] = 1, 1  // the empty floor, and one tile across
	for k := 2; k <= n; k++ {
		// int has 32 or 64 bits, and the sum of two residues is below 2,000,000,014 either way.
		ways[k] = (ways[k-1] + ways[k-2]) % MOD
	}
	return ways[n]
}

func main() {
	for _, n := range []int{1, 2, 3, 4, 10, 50, 1_000_000} {
		fmt.Printf("tilings(%d) = %d\n", n, tilings(n))
	}
}

from session import run, versions

# The verandah count in Java, C++ (built with the sanitizers on) and Go, each on the same seven sizes.
versions("java -version", "clang++ --version", "go version")
run("""
java Tilings.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined tilings.cpp -o tilings && ./tilings
go run tilings.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Tilings.java
tilings(1) = 1
tilings(2) = 2
tilings(3) = 3
tilings(4) = 5
tilings(10) = 89
tilings(50) = 365010934
tilings(1000000) = 534400663
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined tilings.cpp -o tilings && ./tilings
tilings(1) = 1
tilings(2) = 2
tilings(3) = 3
tilings(4) = 5
tilings(10) = 89
tilings(50) = 365010934
tilings(1000000) = 534400663
$ go run tilings.go
tilings(1) = 1
tilings(2) = 2
tilings(3) = 3
tilings(4) = 5
tilings(10) = 89
tilings(50) = 365010934
tilings(1000000) = 534400663

All five print the same seven answers. The sum of two residues is at most 2,000,000,012, and each language holds it exactly in its everyday integer type:

• Python integers have unlimited precision.
• JavaScript numbers are exact for every integer up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1, about 9 × 10¹⁵.
• Java’s int holds values up to 2,147,483,647, by the Java Language Specification, so the sum fits before the remainder is taken. The Java file needs no separate compile step: since Java 11 the java launcher accepts a single source file and compiles it in memory before running it (JEP 330).
• C++ uses int as well, and the static_assert makes the compiler check that int is large enough on the machine that builds it. The build turns on AddressSanitizer and UndefinedBehaviorSanitizer, which report a bad memory access or an overflow while the program runs; this run reported none.
• Go’s int has 32 or 64 bits, depending on the platform, by the Go specification, and either size holds the sum.

A product of two residues would not fit in 32 bits; a later lesson of this module counts with products and shows the types each language needs for them.

Check it against the brute force

"""The table checked against the two versions it came from: the brute force that lists layouts, and the memo."""
from functools import cache

MOD = 1_000_000_007


def brute_force(n):
    """Lists every layout cell by cell, as the backtracking search does, and counts them."""
    floor = [[False] * n, [False] * n]

    def search():
        for col in range(n):
            for row in (0, 1):
                if not floor[row][col]:
                    found = 0
                    for r, c in ((row + 1, col), (row, col + 1)):  # a tile across, or a tile along
                        if r <= 1 and c < n and not floor[r][c]:
                            floor[row][col] = floor[r][c] = True
                            found += search()
                            floor[row][col] = floor[r][c] = False
                    return found
        return 1  # no empty cell is left: one complete layout

    return search()


@cache
def memo(n):
    return 1 if n <= 1 else (memo(n - 1) + memo(n - 2)) % MOD


def table(n):
    ways = [0] * (n + 1)
    ways[0] = ways[1] = 1
    for k in range(2, n + 1):
        ways[k] = (ways[k - 1] + ways[k - 2]) % MOD
    return ways[n]


def two_variables(n):
    before, last = 1, 1
    for _ in range(n - 1):
        before, last = last, (before + last) % MOD
    return last


print("brute force = table, n = 1 to 20:", all(brute_force(n) == table(n) for n in range(1, 21)),
      f"(n = 20 has {brute_force(20):,} layouts)")
# memo(n) is called for n = 1, 2, 3 … in turn: each call finds n - 1 and n - 2 cached, so it never recurses deeply.
print("memo = table, n = 1 to 900:", all(memo(n) == table(n) for n in range(1, 901)))
print("two variables = table, n = 1 to 3,000 and n = 1,000,000:",
      all(two_variables(n) == table(n) for n in [*range(1, 3_001), 1_000_000]))

brute force = table, n = 1 to 20: True (n = 20 has 10,946 layouts)
memo = table, n = 1 to 900: True
two variables = table, n = 1 to 3,000 and n = 1,000,000: True

The listing is the slowest version and the easiest to trust, so it judges the table for every n up to 20, where the counts are still smaller than the modulus. The memo checks the table up to 900, and the two-variable version checks it up to 3,000 and at a million. Notice how the check calls the memo: for n = 1, 2, 3 and so on, in turn. Each call finds n − 1 and n − 2 in the cache already and never goes more than two calls deep, so calling a memoised function on growing inputs is a way to stay under the recursion limit when you must keep the recursion.

The cost

The listing makes a few calls per layout and scans the floor for its first empty cell in each, so its time is the number of layouts, about φⁿ, times n. The plain recursion makes 2 × tilings(n) − 1 calls, and both recursions keep up to n calls open, which is their O(n) space. The memo and the table do O(n) work for the same reason: there are n + 1 states and each costs a constant amount of work beyond the calls it makes. That is the general rule, and the next section takes it apart.

Edge cases and common bugs

• ways[0] is 1, not 0. The limits start at n = 1, but the recurrence reads the empty floor. Making it 0 because “there is nothing to tile” gives 1 layout for n = 2, and the listing shows 2.
• n = 0. ways[0] = ways[1] = 1 writes two entries, which a table of n + 1 entries has only when n ≥ 1. If 0 is allowed, return 1 for it before building the table.
• Reducing only at the end is right in Python but slow, and wrong in the other four languages: the exact counts stop being exact in a JavaScript number from n = 78, and overflow a 64-bit integer from n = 92.
• The wrong loop order, such as filling k from n down to 2 while reading k − 1 and k − 2, reads entries that are still 0.
• A cache made inside the recursive function is a new, empty dictionary on every call, so nothing is ever found in it, and the recursion stays exponential.

States times work: the cost of any DP

Every memoised function and every table has the same cost formula: the number of states it can reach, times the work done for one state, not counting the work of the states it asks for, which are counted on their own. A state is one combination of the arguments that change between calls. Read both numbers off the code:

Two cautions come with the formula. The work per state includes building the key: a key that is a slice or a copy of the input costs as much as the copy, which the next section measures. And the memory follows the same rule, the number of states times the size of one stored answer, plus the depth of the recursion for a memo. Then compare the total with the limits, as the lesson on constraints does for any algorithm. A million states with constant work fits in a second in every language; a grid of 5,000 × 5,000 cells is 25 million states, comfortable in C++ and slow in Python, where its table also needs hundreds of megabytes.

Memoising in Python: keys that work

The cache is a dictionary, so its keys, the arguments, must be hashable, and the Python documentation says plainly that mutable containers such as lists are not. A recursion that passes what is left of the input as a list fails on its first call:

"""Memoising a function that takes a list: TypeError, then a tuple key that works, then the key that is really needed."""
from functools import cache


@cache
def tilings_list(columns):
    """columns: one entry for each column of floor still to cover (only how many there are matters)."""
    if len(columns) <= 1:
        return 1
    return tilings_list(columns[1:]) + tilings_list(columns[2:])


try:
    tilings_list(["empty"] * 30)
except TypeError as error:
    print("a list as the argument:", type(error).__name__ + ":", error)


@cache
def tilings_tuple(columns):
    """The same with a tuple, which can be hashed: it works, but every call copies the rest of the floor."""
    if len(columns) <= 1:
        return 1
    return tilings_tuple(columns[1:]) + tilings_tuple(columns[2:])


@cache
def tilings_length(k):
    """Only the number of columns left matters, so one integer is the whole key."""
    if k <= 1:
        return 1
    return tilings_length(k - 1) + tilings_length(k - 2)


n = 200  # small enough for the cached recursion to run in the browser's Python as well
print("tuple key: ", tilings_tuple(("empty",) * n) == tilings_length(n), tilings_tuple.cache_info())
print("length key:", tilings_length.cache_info())
# One key per length from 0 to n is cached: a tuple key of length L holds L entries.
print(f"the tuple keys hold {sum(range(n + 1)):,} entries in all; the length keys are {n + 1} integers")

a list as the argument: TypeError: unhashable type: 'list'
tuple key:  True CacheInfo(hits=198, misses=201, maxsize=None, currsize=201)
length key: CacheInfo(hits=198, misses=201, maxsize=None, currsize=201)
the tuple keys hold 20,100 entries in all; the length keys are 201 integers

A tuple can be hashed, and the tuple version gives the right answer. It is still the wrong key. Every call slices off a new tuple for the floor that is left, which copies it, so each call costs O(n) instead of O(1), and the cache keeps every one of those tuples: for n = 200, 201 keys holding 20,100 entries in all, where 201 small integers carry the same information. The total grows with the square of n, so at n = 2,000 the tuples would hold 2,001,000 entries. The values in the list never mattered, only how many there were. Before you cache a function, go through its arguments. One that never changes belongs outside the function, in a variable it can see. One that changes should be cut down to the smallest thing the answer depends on: an index, a length, a count.

A cache also outlives the call that filled it. The documentation says that it keeps references to the arguments and the results until it is cleared, so a cached function defined at the top of a file keeps its answers until cache_clear() is called. If those answers depend on anything other than the arguments, such as a grid read from the input, the second test case of an online assessment gets the first test case’s answers. Define the cached function inside the function that solves one case, or call cache_clear() between cases.

Exercise

layouts(1)  # 1
layouts(2)  # 3
layouts(3)  # 5

MOD = 1_000_000_007


def layouts(n):
    """The number of ways to cover a 2 x n floor with 1 x 2 tiles and 2 x 2 slabs, modulo MOD."""
    # Replace this line with your code.
    return 0

from slabs import layouts

MOD = 1_000_000_007


def listed(n):
    """The answer the tests trust for small floors: every layout built cell by cell, as in the lesson, and counted."""
    floor = [[False] * n, [False] * n]

    def fits(cells):
        return all(r <= 1 and c < n and not floor[r][c] for r, c in cells)

    def search():
        for col in range(n):
            for row in (0, 1):
                if not floor[row][col]:
                    pieces = [
                        [(row, col), (row + 1, col)],  # a tile across
                        [(row, col), (row, col + 1)],  # a tile along
                        [(row, col), (row + 1, col), (row, col + 1), (row + 1, col + 1)],  # a slab
                    ]
                    found = 0
                    for cells in pieces:
                        if fits(cells):
                            for r, c in cells:
                                floor[r][c] = True
                            found += search()
                            for r, c in cells:
                                floor[r][c] = False
                    return found
        return 1  # every cell is covered: one complete layout

    return search()


def test_the_examples():
    """the examples of the prompt"""
    assert [layouts(n) for n in (1, 2, 3)] == [1, 3, 5]


def test_small_floors_against_a_listing():
    """n = 1 to 12, each compared with a count of every layout listed one by one"""
    for n in range(1, 13):
        assert layouts(n) == listed(n), f"n = {n}"


def test_counts_above_the_modulus():
    """n = 40 has 733,007,751,851 layouts, which is 7,746,720 modulo 1,000,000,007"""
    assert layouts(40) == 733_007_751_851 % MOD


def test_a_million_columns():
    """n = 1,000,000, too deep for any recursion: fill a table or keep two values"""
    assert layouts(1_000_000) == 490_028_042

export const MOD = 1_000_000_007;

/** The number of ways to cover a 2 x n floor with 1 x 2 tiles and 2 x 2 slabs, modulo MOD. */
export function layouts(n) {
  // Replace this line with your code.
  return 0;
}

import { test, assert } from 'mysmartcopilot:test';
import { layouts } from './slabs.mjs';

const MOD = 1_000_000_007;

/** The answer the tests trust for small floors: every layout built cell by cell, as in the lesson, and counted. */
function listed(n) {
  const floor = [new Array(n).fill(false), new Array(n).fill(false)];
  const fits = (cells) => cells.every(([r, c]) => r <= 1 && c < n && !floor[r][c]);
  const set = (cells, value) => cells.forEach(([r, c]) => (floor[r][c] = value));
  function search() {
    for (let col = 0; col < n; col++) {
      for (const row of [0, 1]) {
        if (floor[row][col]) continue;
        const pieces = [
          [[row, col], [row + 1, col]], // a tile across
          [[row, col], [row, col + 1]], // a tile along
          [[row, col], [row + 1, col], [row, col + 1], [row + 1, col + 1]], // a slab
        ];
        let found = 0;
        for (const cells of pieces) {
          if (!fits(cells)) continue;
          set(cells, true);
          found += search();
          set(cells, false);
        }
        return found;
      }
    }
    return 1; // every cell is covered: one complete layout
  }
  return search();
}

test('the examples of the prompt', () => {
  assert.deepEqual([1, 2, 3].map((n) => layouts(n)), [1, 3, 5]);
});

test('n = 1 to 12, each compared with a count of every layout listed one by one', () => {
  for (let n = 1; n <= 12; n++) assert.equal(layouts(n), listed(n), `n = ${n}`);
});

test('n = 40 has 733,007,751,851 layouts, which is 7,746,720 modulo 1,000,000,007', () => {
  assert.equal(layouts(40), 733_007_751_851 % MOD);
});

test('n = 1,000,000, too deep for any recursion: fill a table or keep two values', () => {
  assert.equal(layouts(1_000_000), 490_028_042);
});

Interview questions

Fresher · What is the difference between memoisation and tabulation, and when would you choose each?

Both keep the answer to each subproblem so that it is worked out only once; they differ in who decides the order. Memoisation keeps the recursive solution and adds a cache keyed by the arguments: the recursion asks for subproblems as it needs them, top-down, and computes only the states the first call reaches. Tabulation fills a table in a loop, bottom-up, in an order where every entry comes after the entries it reads. Choose memoisation when the recursion is already written and tested, when many states are never reached, or when the order is hard to see. Choose tabulation when the recursion would be deep, since a loop has no depth limit, when nearly every state is needed, or when keeping only the last row or two saves memory. In CPython, with its default limit of 1,000 frames, long inputs need the table.

Fresher · How do you work out the time complexity of a dynamic-programming solution?

Count the states and multiply by the work done for one state, leaving out the work of the states it asks for, which are counted on their own. A state is one combination of the arguments that change between calls. For the verandah count the state is the length of floor left: n + 1 states, each doing two lookups and an addition, so O(n) in all. A table over pairs (i, j), with i up to n and j up to m, whose entries each try k choices, costs O(n · m · k). Building a key, such as a slice or a copied tuple, is part of the work per state. Memory follows the same rule: the states times the size of one answer, plus the recursion’s depth for a memo. Then compare the total with the input limits.

Key takeaways

• A recursion whose calls repeat is dynamic programming waiting for a cache. Count the calls per argument to see the repeats: 2,692,537 calls for the 31 lengths of n = 30.
• Memoise first (top-down): keep each answer under its arguments. The memoised count made 59 calls for n = 30.
• Tabulate when the recursion is deep or every state is needed (bottom-up): one entry per state, the base cases first, and every entry after the entries it reads. A loop has no depth limit; CPython’s recursion limit is 1,000 by default.
• The cost of any DP is its number of states times the work per state, and its memory is the states times the size of one answer, plus the depth for a memo.
• Reduce modulo after every addition: exact counts stop being exact in a JavaScript number from n = 78 and overflow a 64-bit integer from n = 92, and in Python they grow by about 0.69 bits per column and slow the loop down.
• Cache on the smallest key the answer depends on. A list cannot be a key of functools.cache; a tuple can, but copying the input into a key on every call costs O(n) per call.