Skip to content

Counting Tilings

Tiling problems ask how many ways to cover a region (often a \(1 \times n\) or \(2 \times n\) board) with tiles of given shapes—dominoes, trominoes, etc. States usually encode how the boundary looks after filling a prefix; DP runs over position or profile (profile DP / transfer matrix on a strip).

Fibonacci-style: dominoes on \(1 \times n\)

Place \(1 \times 2\) dominoes (horizontal) and \(2 \times 1\) would need two rows—on a \(1 \times n\) strip with only \(1 \times 1\) and \(1 \times 2\) tiles, counts follow a linear recurrence (often Fibonacci). On \(2 \times n\) with \(2 \times 1\) dominoes, the number of tilings is also the Fibonacci sequence (classic).

\(2 \times n\) domino tiling

Let dp[n] = ways to tile a 2 x n grid with 2x1 and 1x2 dominoes.

#include <vector>
using namespace std;

long long dominoTiling2xn(int n) {
    if (n <= 1) return 1;
    vector<long long> dp(n + 1);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

(Concrete boundary conditions depend on whether you count n=0 as 1.)

Profile DP (sketch)

For \(m \times n\) with small \(m\), represent each column (or step) by a mask of which cells are “sticking out” from the unfinished tiling. Transitions enumerate how to place the next tile slice. Complexity is exponential in \(m\) but polynomial in \(n\).

// State = bitmask of height m; transition(next_mask) for valid tile placements.
// See Bitmask DP for manipulating small state masks.