790: Domino-and-Tromino-Tiling
Medium

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:

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