379. In how many ways can a 2 × n board be tiled with 1 × 2 dominoes?
EasyDynamic programming
Technical
Show model answer
Look at the left edge: either a vertical domino covers the first column, leaving a 2 × (n − 1) board, or two horizontal dominoes cover the first two columns, leaving 2 × (n − 2). So f(n) = f(n − 1) + f(n − 2) with f(0) = 1 and f(1) = 1, the Fibonacci numbers 1, 2, 3, 5, 8, ... for n = 1, 2, 3, ... O(n) time, O(1) space, or O(log n) with matrix powers.
The same thinking extends to harder boards. A 3 × n board has 0 tilings for odd n and satisfies f(n) = 4·f(n − 2) − f(n − 4) for even n (1, 3, 11, 41, ...). For general m × n boards, use DP over the column profile as a bitmask.