Domino and Tromino Tiling

The key idea

Let f(n) count the ways to FULLY tile a 2 x n board. Track a second state p(n) for a board with one extra protruding cell (the typical state after placing a tromino). Solving the two coupled recurrences collapses to the closed recurrence f(n) = 2*f(n-1) + f(n-3).

Problem

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile a 2 x n board. Since the answer may be very large, return it modulo 10^9 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Constraints

1 <= n <= 1000

Examples

Input: n = 3 Output: 5

Input: n = 1 Output: 1

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →