101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming with Multiple States - Complex approach
  2. Dynamic Programming with Recurrence Relation - Complex approach
  3. Matrix Exponentiation - Complex approach

Approach 1: Dynamic Programming with Multiple States

The key insight for solving this problem is to define multiple states to represent different configurations of the board.

Let's define two DP arrays:

  • dp[i]: the number of ways to completely tile a 2×i board.
  • dp2[i]: the number of ways to tile a 2×i board with a single square protruding from the right (either at the top or bottom).

For dp[i], we can:

  1. Place a vertical domino, which gives dp[i-1] ways.
  2. Place two horizontal dominos, which gives dp[i-2] ways.
  3. Place a tromino in two different orientations, each giving dp2[i-1] ways.

Therefore, dp[i] = dp[i-1] + dp[i-2] + 2 * dp2[i-1].

For dp2[i], we can:

  1. Place a horizontal domino, which gives dp2[i-1] ways.
  2. Place a tromino, which gives dp[i-2] ways.

Therefore, dp2[i] = dp2[i-1] + dp[i-2].

The base cases are:

  • dp[0] = 1 (there is one way to tile an empty board)
  • dp[1] = 1 (there is one way to tile a 2×1 board with a vertical domino)
  • dp2[0] = 0 (there is no way to tile an empty board with a protruding square)
  • dp2[1] = 1 (there is one way to tile a 2×1 board with a protruding square)

We can use a bottom-up approach to fill the DP arrays from the base cases up to n.

Algorithm:

  1. Initialize dp[0] = 1, dp[1] = 1, dp2[0] = 0, dp2[1] = 1.
  2. For i from 2 to n:
  3. a. Compute dp2[i] = (dp2[i-1] + dp[i-2]) % MOD.
  4. b. Compute dp[i] = (dp[i-1] + dp[i-2] + 2 * dp2[i-1]) % MOD.
  5. Return dp[n].

Time Complexity:

O(n)

We need to compute the DP values for each i from 2 to n, which requires a constant amount of work for each i.

Space Complexity:

O(n)

We use two DP arrays of size n+1 to store the number of ways to tile the board in different configurations.

Approach 2: Dynamic Programming with Recurrence Relation

Another approach is to derive a direct recurrence relation for the number of ways to tile a 2×n board.

Let's define dp[i] as the number of ways to tile a 2×i board.

After analyzing the problem, we can derive the following recurrence relation:

dp[i] = 2 * dp[i-1] + dp[i-3] for i >= 4

The base cases are:

  • dp[1] = 1
  • dp[2] = 2
  • dp[3] = 5

This recurrence relation can be derived by considering the different ways to place tiles at the right edge of the board.

Algorithm:

  1. Initialize dp[1] = 1, dp[2] = 2, dp[3] = 5.
  2. For i from 4 to n:
  3. a. Compute dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD.
  4. Return dp[n].

Time Complexity:

O(n)

We need to compute the DP values for each i from 4 to n, which requires a constant amount of work for each i.

Space Complexity:

O(n)

We use a DP array of size n+1 to store the number of ways to tile the board.

Approach 3: Matrix Exponentiation

For large values of n, we can use matrix exponentiation to compute the result more efficiently.

The recurrence relation dp[i] = 2 * dp[i-1] + dp[i-3] can be represented using a 3×3 matrix:

[2 0 1] [dp[i-1]] [dp[i]]
[1 0 0] * [dp[i-2]] = [dp[i-1]]
[0 1 0] [dp[i-3]] [dp[i-2]]

By computing this matrix raised to the power of n-3, we can find the value of dp[n].

Matrix exponentiation can be done in O(log n) time using the binary exponentiation algorithm.

Algorithm:

  1. If n is 1, return 1. If n is 2, return 2. If n is 3, return 5.
  2. Define a 3×3 matrix base = [[2, 0, 1], [1, 0, 0], [0, 1, 0]].
  3. Compute base^(n-3) using binary exponentiation.
  4. Multiply the result with the vector [5, 2, 1] to get [dp[n], dp[n-1], dp[n-2]].
  5. Return dp[n].

Time Complexity:

O(log n)

Using binary exponentiation, we can compute the matrix power in logarithmic time.

Space Complexity:

O(1)

We only use a constant amount of space to store the 3×3 matrices.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function numTilings(n):
    MOD = 10^9 + 7
 
    // Base cases
    if n == 1:
        return 1
 
    // Initialize DP arrays
    dp = new array of size n+1
    dp2 = new array of size n+1
 
    dp[0] = 1
    dp[1] = 1
    dp2[0] = 0
    dp2[1] = 1
 
    // Fill DP arrays
    for i from 2 to n:
        dp2[i] = (dp2[i-1] + dp[i-2]) % MOD
        dp[i] = (dp[i-1] + dp[i-2] + 2 * dp2[i-1]) % MOD
 
    return dp[n]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone