Domino and Tromino Tiling

medium dp recurrence

Problem

We have two types of tiles: a 2x1 domino shape, and an "L" tromino shape. These shapes may be rotated. XX <- domino XX <- "L" tromino X Given N, how many ways are there to tile a 2 x N board?

Inputn = 4

Output11

Trace the recurrence: dp[3]=5, dp[4]=2·5+1=11.

def num_tilings(n):
    if n == 0: return 1
    if n <= 2: return n
    dp = [1, 1, 2]
    for i in range(3, n + 1):
        dp.append(2 * dp[i - 1] + dp[i - 3])
    return dp[n]

function numTilings(n) {
  if (n === 0) return 1;
  if (n <= 2) return n;
  const dp = [1, 1, 2];
  for (let i = 3; i <= n; i++) dp.push(2 * dp[i - 1] + dp[i - 3]);
  return dp[n];
}

class Solution {
    public int numTilings(int n) {
        if (n == 0) return 1;
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 1; dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) dp[i] = 2 * dp[i - 1] + dp[i - 3];
        return dp[n];
    }
}

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

Explanation

We are tiling a 2-by-n board with dominoes and L-shaped trominoes, and we want the number of full tilings. Working out the cases carefully leads to a surprisingly tidy recurrence: dp[i] = 2·dp[i-1] + dp[i-3].

Here dp[i] is the number of ways to tile a 2×i board. The 2·dp[i-1] term covers adding a clean vertical edge or one of the two tromino orientations that extend a previously-solved board, and the + dp[i-3] term accounts for the extra fully-flat fillings that only appear three columns back.

We seed the small cases directly: dp[0] = 1, dp[1] = 1, dp[2] = 2, then build upward.

Example: n = 4. We have dp[3] = 2·dp[2] + dp[0] = 2·2 + 1 = 5, then dp[4] = 2·dp[3] + dp[1] = 2·5 + 1 = 11, which is the answer.

Each dp[i] is one quick formula using earlier values, so computing up to n is a single linear pass.

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