Domino and Tromino Tilings

medium dp recurrence

Problem

Count the number of ways to tile a 2 × n strip with 2×1 dominoes (vertical or horizontal) and L-shaped trominoes (each covers three squares). The recurrence is dp[n] = 2·dp[n−1] + dp[n−3] with dp[0]=1, dp[1]=1, dp[2]=2.

Inputn = 4

Output11

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

def 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 tilings(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 tilings(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 tilings(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];
}

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