Domino and Tromino Tiling
Medium · Dynamic Programming · about 25 minutes
Asked at Google, Amazon, Meta, Bloomberg.
Count the ways to tile a 2 × n board with 2 × 1 dominoes and L-shaped trominoes (both may be rotated). Return the count modulo 10⁹ + 7.