Tiling dominoes count

Count the number of ways to tile a 2 x n board with 2 x 1 dominoes.

dynamic-programming fibonacci counting math

Write a function `count_tilings(n: int) -> int` that returns the number of distinct ways to tile a 2 by n board with 2 by 1 dominoes. Dominoes can be placed either vertically (covering 2 rows and 1 column) or horizontally (covering 1 row and 2 columns). Rotations are allowed. The board is exactly 2 units high and n units wide. For example, a 2 by 3 board has three tilings: all vertical, one vertical with two horizontal stacked, and two horizontal stacked with one vertical. The answer fits in a 32-bit signed integer for all valid n.

Constraints

0 ≤ n ≤ 30

Example

>>> count_tilings(0)
1
>>> count_tilings(1)
1
>>> count_tilings(2)
2
>>> count_tilings(3)
3
>>> count_tilings(4)
5

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the last column: either a vertical domino or two horizontal dominoes.

Define the recurrence based on the number of columns remaining.

Use iteration (bottom-up DP) or memoization.

The sequence is the Fibonacci numbers (shifted).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.