Number of Ways to Tile a 2×N Board with 2×1 Dominoes

Problem

Count the number of ways to completely fill a 2×N board using 2×1 dominoes (placed horizontally or vertically).

Example

N=1 → 1 way
N=2 → 2 ways
N=3 → 3 ways
N=4 → 5 ways

This follows the Fibonacci sequence: f(n) = f(n-1) + f(n-2).

Follow-up variants Adobe asks

1. 3×N board with 1×3 and 3×1 tiles
2. M×N board (general case) — use profile DP / bitmask DP
3. Count only distinct tilings under rotation

Hint for 3×N

Use bitmask DP where the state represents which cells in the current column are already filled by tiles from the previous column.