Problem Statement

Given a 3 x n board, find the number of ways to fill it with 2 x 1 dominoes.

Example 1

Following are all the

3

possible ways to fill up a

3 x 2

board.

Example 2

Here is one possible way of filling a 3 x 8 board. You have to find all the possible ways to do so.

Examples :

Input : 2
Output : 3

Input : 8
Output : 153

Input : 12
Output : 2131

Problem Link

Tiling With Dominoes - InterviewBit

Reference Link

Tiling with Dominoes - GeeksforGeeks

Code

#define mod 1000000007

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