Show problems as
Classic problem #790MediumDynamic Programming

Domino and Tromino Tiling

Real-world version: Leading a Two-Pane Transom
Tracked in this browser only
Read Domino and Tromino Tiling on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A glazier is re-leading a transom window that stands two panes tall and n panes wide, so the frame holds 2 * n panes arranged in two rows.

Two came shapes are on the bench, and the workshop has an unlimited supply of each:

  • a bar, which grips two panes sharing an edge: either two neighbours in the same row, or the two panes of a single column;
  • an elbow, which grips the three panes that remain when one pane is lifted out of a two-by-two square of panes.

Either shape may be rotated freely before it is laid down. Every pane of the frame must end up gripped by exactly one shape, and no shape may reach beyond the frame.

Count the ways to lead the whole transom. Two leadings differ when some pair of panes is gripped by one shape in the first and by two different shapes in the second. The tally climbs steeply with n, so return the remainder it leaves after division by 1000000007.

Examples

Example 1

Input
n = 2
Output
2

Two leadings cover the four panes: an upright bar in each column, or a sideways bar along each row. Any elbow laid here leaves a single pane that nothing can grip.

Example 2

Input
n = 4
Output
11

Eleven leadings cover the eight panes. One of them puts an upright bar in the leftmost column and a pair of locked elbows across the other columns.

Example 3

Input
n = 5
Output
24

Twenty-four leadings cover the ten panes. One lays a sideways bar along each row of the two leftmost columns and locks two elbows into the rest.

Example 4

Input
n = 6
Output
53

Fifty-three leadings cover the twelve panes, among them an upright bar in each of the first three columns with two locked elbows filling the rest.

Constraints

  • 1 <= n <= 1000
  • The returned value is the tally reduced modulo 1000000007.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def num_tilings(n: int) -> int:
Java
public int numTilings(int n)

More on the same topics