A different puzzle with a familiar answer

Picture a long, narrow hallway floor, 2 tiles tall and n tiles long, and a pile of dominoes that each cover two tiles. A domino can stand upright and fill one column, or two can lie flat, one on top of the other, and fill two columns. How many ways can you cover the whole floor?

Use the stairs trick: look at the far end. Either one upright domino covers the last column, leaving a floor one shorter, or two flat dominoes cover the last two columns, leaving a floor two shorter.

It's the stairs again: the answer for n adds the answers for n − 1 and n − 2.

Different story, same maths: learning to spot that is half of DP.

Fill a table from the small end

This time, skip the recursion entirely. Start with the answers you already know: an empty floor can be covered in exactly 1 way (do nothing), and a floor 1 tile long in exactly 1 way (one upright domino).

Then work out length 2, then length 3, and so on, each from the two answers just before it. When you reach length n, the answer is waiting for you. No repeated questions and no notebook lookups, just a row filled in from left to right. This is called tabulation, or bottom-up DP.

Smallest first: every answer you need is already in the table.

Two roads, same place: memoization and tabulation give the same answers.

In code

ways = [0] * (n + 1)
ways[0] = 1
if n >= 1:
    ways[1] = 1
for i in range(2, n + 1):
    ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]

Tilings of a 2 × n board, filled from the smallest n up

n = 0n = 1n = 2n = 3

ways

Start from what we know: an empty board has 1 tiling (do nothing), and a 2 × 1 board has 1 (one upright domino).

Move 1 of 3