DSA Factory
Free lessonsDynamic programming · Stage 0 · Remember answers · Step 2

Tiling a 2×n board

Instead of recursing top-down with a cache, build the answer bottom-up in a plain array. About 10 minutes.

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
1
1

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
Quick check

You're filling the table from the left. What must already be filled in before you work out the answer for length 5?

  1. AThe answers for lengths 4 and 3
  2. BThe answer for length 6
Show the answer

The answers for lengths 4 and 3. You fill left to right, so both are already there when you reach length 5.

Your problem

Tiling a 2×n board

You have a 2×n board and an unlimited supply of 1×2 dominoes, which can be placed upright (covering one column) or lying flat (covering two columns, one on top of the other). Return the number of distinct ways to fully tile the board.

Example
n = 3 → 3

0 ≤ n ≤ 75

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding