Dominos Arrangement

Intution: Lets denote U[n] is the number of ways to fill the box of size 3*N using the dominos.

and V[n] is defined as the number ways to fill the 3*n rectangle box without a lower left corner.

U[n] can be break into smaller subproblems as  U[n-2] + V[n-1] + V[n-1] shown in the figure below.

V[n] can be similarly break into smaller subproblems as V[n-2] +U[n-1] shown in the figure below.

So, using these all relations ,the final recursive realtion is U[n] = U[n-2] + 2*V[n-1] and V[n] = U[n-1] + V[n-2].

Base Cases will be :

So, using these equations we will define two functions findU(n) that will return the value of U[n] and findV(n) that will return the value of V[n] as described above.At last,we will return the value of findU(n) corresponding to the final answer.

Algorithm:

• Define findU(n) function that will return the number of ways to fill the box of size 3*N using the dominos.
  • If N==1:
    • Return 0.
  • If N==2:
    • Return 3.
  • Return ( findU(n-2) + 2*findV(n-1))% (10^9 +7).
• Define findV(n) function that will return the number of ways to fill the 3*n rectangle box without lower-left corners.
  • If N==1:
    • Return 1.
  • If N==2:
    • Return 0.
  • Return ( findV(n-2) + findU(n-1))% (10^9 +7).
• Return findU(n) corresponding to the final answer.

In approach 1, we used recursive approach to calculate the answer.

In this approach, we will use the same recursive function and will memoize the solution to reduce the time complexity.

So, using these equations we will define two functions findU(n) that will return the value of U[n] and findV(n) that will return the value of V[n] as described in Approach 1 and store the values in U[n] and V[n] respectively. At last, we will return the value of findU(n) corresponding to the final answer.

Algorithm:

• Define findU(‘N’,’U’,’V’) function that will return the number of ways to fill the box of size 3*N using the dominos.
  • If N==1:
    • Return 0.
  • If N==2:
    • Return 3.
  • If U[N] is not equal to -1:
    • Return U[N].
  • Set U[N] as ( findU(N-2,U,V) + ( 2*findV(N-1,V,U))% (10^9 +7) )% (10^9 +7) .
  • Return U[N].
• Define findV(‘N’,’V’,’U’) function that will return the number of ways to fill the 3*n rectangle box without lower-left corners.
  • If N==1:
    • Return 1.
  • If N==2:
    • Return 0.
  • If V[N] is not equal to -1:
    • Return V[N].
  • Set V[N] as ( findV(N-2,V,U) + findU(N-1,U,V))% (10^9 +7).
  • Return V[N].

• Declare U and V of size (N+1) each to memoize the answers.
• Set all values of U and V to -1.
• Return findU(n,U,V) corresponding to the final answer.

As we discussed the relations in approach 1, we will declare two arrays U and V to store the values corresponding to U[i] and V[i] in these arrays. So first we will set the base case values and then we will iterate from 3 to N and find the values of U[i] and V[i] using the equations and at last, we will return U[N] as the final answer.

Algorithm:

• Declare two arrays ‘U’ and ‘V’ of size ‘N+1’ to store the answers for the subproblems.
• Set the base cases.
• Set U[1] as 0.
• Set U[2] as 3.
• Set V[1] as 1.
• Set V[2] as 0.
• For i in range 3 to N:
  • Set U[i] as ( U[i-2] + ( 2*V[i-1])% (10^9 +7) )% (10^9 +7).
  • Set V[i] as ( V[i-2] + U[i-1])% (10^9 +7).
• All values are computed.
• Return U[n].