790. Domino and Tromino Tiling

Description of Problem

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 10^9 + 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 show above.

Example 2:

Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 1000

Solution

Tags: Dynamic Programming

Explanation

Picture of Explanation

Code (Rust)

impl Solution {
    pub fn num_tilings(n: i32) -> i32 {
        const MOD : u64 = 1_000_000_007;
        let n = n as usize;
        let mut lambda  = vec![0 ; 3];
        let mut mu = vec![0 ; 3];
        
        for i in 1..=2 {
            if n >= i{
                lambda[i % 3] = i as u64;
                mu[i % 3] = i as u64;
            }
        }

        for i in 3..=n{
            lambda[i % 3] = 
                (lambda[(i - 1) % 3] ) % MOD 
                + (lambda[(i - 2) % 3] ) % MOD 
                + (2 * mu[(i - 2) % 3] ) % MOD;
            lambda[i % 3] = lambda[i % 3] % MOD;
   
            mu[i % 3] = 
                (mu[(i - 1) % 3]) % MOD 
                + (lambda[(i - 1) % 3]) % MOD;
            mu[i % 3] = mu[i % 3] % MOD;
        }
        return lambda[n % 3] as i32;
    }
}

Complexity

Time Complexity

  • \( T(n) = \Theta(n) \)

Auxiliary Space

  • \( S(n) = \Theta(n) \)
  • \( S(n) = O(1) \) (With Space Optimisation)

Reference