Tiling with Dominoes | Dynamic Programming | InterviewBit Solution | C++ | Java |

 

Problem Description

Given an integer A you have to find the number of ways to fill a 3 x A board with 2 x 1 dominoes. Return the answer modulo 10^9 + 7 .

NOTE:

1. See the sample explanation for better understanding.

 

Problem Constraints:

• 1 <= A <= 10^5

Input Format:

First and only argument is an integer A.

Output Format:

Return an integer denoting the number of ways to fill a 3 x A board with 2 x 1 dominoes with modulo 109 + 7.

Example Input:

Input 1: 

2

Input 1:

1

Example Output: 

Output 1:

3

Output 2: 

0

Example Explanation

Explanation 1:

 Following are all the 3 possible ways to fill up a 3 x 2 board.

          

 Explanation 2:

 Not a even a single way exists to completely fill the grid of size 3 x 1.

 

Approach:

Defining Subproblem:

At any point while filling the board, there are three possible states that the last column can be in:

An =  No. of ways to completely fill a 3 x n board. (We need to find this)

Bn =  No. of ways to fill a 3 x n board with top corner in last column not filled.

Cn =  No. of ways to fill a 3 x n board with bottom corner in last column not filled.

NOTE: The following states are impossible to reach

Finding Recurrences

Note: Even though Bn and Cn are different states, they will be equal for same ‘n’. i.e  Bn = Cn
Hence, we only need to calculate one of them.

Calculating An:

Calculating Bn:

Final Recursive Relations are:

Base Cases:

Problem Solution in C++ Programming Language:

code:

int Solution::solve(int A) {

    if(A%2) return 0;

    vector<long long int> a(A+1, 0), c(A+1,0);

    a[1]=1, c[1]=0, a[2]=0, c[2]=3;

    

    for(int i=3;i<=A;i++){

        c[i]=(2*a[i-1]+c[i-2])%1000000007;

        a[i]=(c[i-1]+a[i-2])%1000000007;

    }

    return c[A];

}

Problem Solution in Java Programming Language:

code:

public class Solution {

    

    

    public int solve(int A) {

        

        if(A%2==1)

            return 0;

        

        int mod = 1000000007;

        

        int mem1[] = new int[100001];

        int mem2[] = new int[100001];

        Arrays.fill(mem1, 0);

        Arrays.fill(mem2, 0);

        

        mem1[2]=3;

        mem2[2]=2;

        for(int i=4; i<=A;i+=2){

            

            mem1[i]= ((mem1[i-2] + (mem1[i-2] + mem1[i-2])%mod)%mod 

                                        + mem2[i-2])%mod;

            mem2[i] = ((mem1[i-2] + mem1[i-2])%mod + 

                                        mem2[i-2])%mod;

            

            

        }

        

/*        for(int i=0;i<=A; i++){

            System.out.print(mem1[i] + " ");

        }        

        System.out.println();

        for(int i=0;i<=A; i++){

            System.out.print(mem2[i] + " ");

        }

        System.out.println();

        */

        return mem1[A];

        

    }

}

Thank you for reading.

For any questions, feedback and query comment below.

Keep coding!.