Domino and Tromino - Simplified Recurrence

By symmetry, $g[i] = h[i]$ always (the two uneven profiles have the same count). Let $p[i] = f[i]$ (flush profile count) and $q[i] = g[i]$ (uneven profile count). Then $p[i+1] = 2p[i] + 2q[i]$ and $q[i+1] = p[i] + q[i]$. You can combine these into a single recurrence for $p[i]$: $p[i] = 2p[i-1] + p[i-3]$.

This lets you compute the answer in $O(n)$ time with a simple loop. The broken profile perspective reveals why this recurrence works. Without it, deriving the formula by hand is tricky.