hardDynamic Programming 1DPure DSA~30 min
Tilings of a 2 x N Board with Dominoes and Trominoes
A 2-row layout grid of width n must be tiled completely using 2x1 dominoes (either orientation) and L-shaped trominoes. Count the number of distinct full tilings.
Problem
Given an integer n, count the number of ways to fully tile a 2 x n board using 2x1 dominoes and L-shaped trominoes (each may be rotated). Two tilings are different if some cell is covered by differently oriented or different pieces. Return the count modulo 1e9 + 7.
Input
An integer n (board width).
Output
An integer: the number of tilings modulo 1e9 + 7.
Constraints
- 1 <= n <= 1000
Examples
Example 1
Input
n = 3
Output
5
There are 5 ways to tile a 2x3 board.
Example 2
Input
n = 1
Output
1
Only a single vertical domino fits a 2x1 board.