Complexity Analysis

Time: $O(m \cdot 2^n \cdot T)$, where $m$ is columns, $n$ is rows, and $T$ is average transitions per profile. For typical tiling, $T$ is small (constant or logarithmic in $2^n$). Space: $O(2^n)$ with a rolling array (store only current and previous column), otherwise $O(m \cdot 2^n)$.

With $n \leq 10$, $2^n \leq 1024$, which fits easily. Precomputing transitions takes $O(2^n \cdot 2^n)$ worst case, but practice is faster because not all transitions are valid.