Domino and Tromino Tiling

This is basically just a math question.

If we let nT(n) be the number of possible tilings of size n, we can see that it is equal to the sum of:

nT(n-1) + | (a vertical dominoes)

nT(n-2) + = (2 horizontal dominoes)

nT(n-3) + {L⅂ , Γ⅃} (2 variations of trominoes)

nT(n-4) + {L‾⅃ , Γ_⅂} (2 variations of trominoes + horizontal dominoes)

nT(n-5) + {L‾_⅂ , Γ_‾⅃} (2 variations of trominoes + horizontal dominoes)

etc.

This infers that the equation below holds:

\begin{align*} &nT(n) = nT(n-1) + nT(n-2) + 2 \times (nT(n-3) + ... + nT(0))\\ &\implies nT(n-1) = nT(n-2) + nT(n-3) + 2 \times (nT(n-4) + ... + nT(0))\\ &\iff nT(n-2) + nT(n-3) = nT(n-1) - 2 \times (nT(n-4) + ... + nT(0)) \end{align*}

Therefore, using the equation above,

\begin{align*} nT(n) &= nT(n-1) + nT(n-2) + 2 \times (nT(n-3) + ... + nT(0))\\ &= nT(n-1) + (nT(n-2) + nT(n-3)) + nt(n-3) + 2 \times (nT(n-4) + ... + nT(0))\\ &= nT(n-1) + (nT(n-1) - 2 \times (nT(n-4) + ... + nT(0))) + nT(n-3) + 2 \times (nT(n-4) + ... + nT(0))\\ &= 2 \times nT(n-1) + nT(n-3)) \end{align*}

meaning this is just a recursive function:

nT(n) = 2 \times nT(n-1) + nT(n-3)

code

class Solution {
public:
    int numTilings(int n) {
        --n;
        vector<int> count = {1, 2, 5};
        if (n < 2) {
            return count[n];
        }
        for (int i = 2; i < n; ++i) {
            count.push_back(count.back()*2 + count[0]);
            count.erase(count.begin());
        }
        return count.back();
    }
};

complexity

Time: O(n) where n is literally the n provided in the question (crazy)

Space: O(1)