Counting Tilings - Walkthrough

Tile an $n \times m$ grid with $1 \times 2$ dominoes. How many ways? $dp[row][mask]$ = number of ways to fill rows $0..row-1$ completely, with current row having profile $mask$. Base: $dp[0][0] = 1$ (empty grid, nothing filled yet). Transition: for each mask, try all ways to fill the row.

Answer: $dp[n][0]$ (all rows filled, final profile is empty). Time: $O(n \cdot 2^m \cdot 2^m)$

Time complexity: $O(n \cdot 4^m)$.

Space complexity: $O(2^m)$ with rolling array, or $O(n \cdot 2^m)$ without.