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 show above.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 1000This problem can be solved using dynamic programming by considering the number of ways to tile smaller sections of the board and building up to solve for larger sections.
Define a DP array where dp[i] represents the number of ways to tile a 2 x i board.
The recurrence relation involves using domino and tromino tiles:
dp[i] = dp[i-1] + dp[i-2] + 2 * sum[dp[j-2] for j in 3 to i]This relation stems from the ways to construct tilings using the previous configurations.
The above code uses dynamic programming to solve the problem, leveraging an array dp[] to keep track of ways to tile boards of increasing lengths.
Initial conditions are dp[0] = 1, dp[1] = 1, and dp[2] = 2. The recurrence relationship derives from placing tiles in ways that affect the size n.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(n).
This solution uses matrix exponentiation to derive the result by considering the recurrence relation characteristic equation derived earlier. This approach is efficient for large n due to the optimization from reducing the problem to matrix multiplications.
The Matrix Exponentiation approach arranges the problem in terms of a transform matrix based on the transition relations derived from examining the problem.
The matrix is exponentiated using fast exponentiation (squaring technique) to efficiently compute powers.
Java
Python
Time Complexity: O(log n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n). |
| Matrix Exponentiation Approach | Time Complexity: O(log n). |
Tiling dominoes | Dynamic programming • WilliamFiset • 44,145 views views
Watch 9 more video solutions →Practice Domino and Tromino Tiling with our built-in code editor and test cases.
Practice on FleetCode