Tiling With Dominoes

• Time : $O(n)$
• Space : $O(n)$

int Solution::solve(int n) {
    vector<long long> A(n + 1), B(n + 1);
    const int mod = 1e9 + 7;
    A[0] = 1, A[1] = 0, B[0] = 0, B[1] = 1;
    for (int i = 2; i <= n; i++) {
        A[i] = A[i - 2] + 2 * B[i - 1];
        B[i] = A[i - 1] + B[i - 2];
        A[i] %= mod;
        B[i] %= mod;
    }

    return A[n];
}