Domino and Tromino - Implementation

Here is the formula-based solution. The formula comes from analyzing profile transitions for the $2$-row board with dominoes and trominoes:

function numTilings(n):
    MOD := 1000000007
    if n = 1 then return 1
    if n = 2 then return 2
    p := array of size n+1
    p[0] := 1
    p[1] := 1
    p[2] := 2
    for i from 3 to n:
        p[i] := (2 * p[i-1] + p[i-3]) mod MOD
    return p[n]

This runs in $O(n)$ time and $O(n)$ space. The formula $p[i] = 2p[i-1] + p[i-3]$ captures all tiling configurations by counting how the two tile types combine.

You could improve to $O(1)$ space by keeping only the last three values.