Domino and tromino tiling

Dynamic Programming

51.4% acceptance

Feb 21, 2026

4140

1316

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 an 2 x n board. Since the answer may be very large, return it modulo 109 + 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

/*
 * 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 an 2 x n board. Since the answer may be very large, return it modulo 109 + 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.
 * Example 1:
 * Input: n = 3
 * Output: 5
 * Explanation: The five different ways are shown above.
 * Example 2:
 * Input: n = 1
 * Output: 1
 * Constraints:
 * 1 <= n <= 1000
 */
impl Solution {
  pub fn num_tilings(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    if n == 1 { return 1; }
    if n == 2 { return 2; }
    let mut dp = vec![0i64; n + 1];
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    for i in 3..=n {
      dp[i] = (2 * dp[i-1] % MOD + dp[i-3]) % MOD;
    }
    dp[n] as i32
  }
}