\\Given a positive integer N, the task is to find the number of ways to fill the board of dimension 2*N with a tile of dimensions 2 × 1, 1 × 2, (also known as domino) and an ‘L‘ shaped tile(also know as tromino) show below that can be rotated by 90 degrees.
The L shape tile: XX X After rotating L shape tile by 90: XX X or X XX
Examples:
Input: N = 3
Output: 5
Explanation:
Below is the image to illustrate all the combinations:
Input: N = 1
Output: 1
Approach: The given problem can be solved based on the following observations by:
Let’s define a 2 state, dynamic programming say dp[i, j] denoting one of the following arrangements in column index i.
- The current column can be filled with 1, 2 × 1 dominos in state 0, if the previous column had state 0.
- The current column can be filled with 2, 1 × 2 dominos horizontally in state 0, if the i – 2 column has state 0.
- The current column can be filled with an ‘L‘ shaped domino in state 1 and state 2, if the previous column had state 0.
- The current column can be filled with 1 × 2 shaped domino in state 1 if the previous column has state 2 or in state 2 if the previous column has state 1.
- Therefore, the transition of the state can be defined as the following:
- dp[i][0] = (dp[i – 1][0] + dp[i – 2][0]+ dp[i – 2][1] + dp[i – 2][2]).
- dp[i][1] = dp[i – 1][0] + dp[i – 1][2].
- dp[i][2] = dp[i – 1][0] + dp[i – 1][1].
Based on the above observations, follow the steps below to solve the problem:
- If the value of N is less than 3, then print N as the total number of ways.
- Initialize a 2-dimensional array, say dp[][3] that stores all the states of the dp.
- Consider the Base Case: dp[0][0] = dp[1][0] = dp[1][1] = dp[1][2] = 1.
- Iterate over the given range [2, N] and using the variable i and perform the following transitions in the dp as:
- dp[i][0] equals (dp[i – 1][0] + dp[i – 2][0]+ dp[i – 2][1] + dp[i – 2][2]).
- dp[i][1] equals dp[i – 1][0] + dp[i – 1][2].
- dp[i][2] equals dp[i – 1][0] + dp[i – 1][1].
- After completing the above steps, print the total number of ways stored in dp[N][0].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const long long MOD = 1e9 + 7;// Function to find the total number// of ways to tile a 2*N board using// the given types of tileint numTilings(int N){ // If N is less than 3 if (N < 3) { return N; } // Store all dp-states vector<vector<long long> > dp( N + 1, vector<long long>(3, 0)); // Base Case dp[0][0] = dp[1][0] = 1; dp[1][1] = dp[1][2] = 1; // Traverse the range [2, N] for (int i = 2; i <= N; i++) { // Update the value of dp[i][0] dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 2][1] + dp[i - 2][2]) % MOD; // Update the value of dp[i][1] dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // Update the value of dp[i][2] dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; } // Return the number of ways as // the value of dp[N][0] return dp[N][0];}// Driver Codeint main(){ int N = 3; cout << numTilings(N); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;class GFG{public static long MOD = 1000000007l;// Function to find the total number// of ways to tile a 2*N board using// the given types of tilepublic static long numTilings(int N) { // If N is less than 3 if (N < 3) { return N; } // Store all dp-states long[][] dp = new long[N + 1][3]; for(long[] row : dp) { Arrays.fill(row, 0); } // Base Case dp[0][0] = dp[1][0] = 1; dp[1][1] = dp[1][2] = 1; // Traverse the range [2, N] for(int i = 2; i <= N; i++) { // Update the value of dp[i][0] dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 2][1] + dp[i - 2][2]) % MOD; // Update the value of dp[i][1] dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // Update the value of dp[i][2] dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; } // Return the number of ways as // the value of dp[N][0] return dp[N][0];}// Driver Codepublic static void main(String args[]){ int N = 3; System.out.println(numTilings(N));}}// This code is contributed by gfgking |
Python3
# Python3 program for the above approache9 + 7;# Function to find the total number# of ways to tile a 2*N board using# the given types of tileMOD = 1e9 + 7def numTilings(N): # If N is less than 3 if (N < 3): return N # Store all dp-states dp = [[0] * 3 for i in range(N + 1)] # Base Case dp[0][0] = dp[1][0] = 1 dp[1][1] = dp[1][2] = 1 # Traverse the range [2, N] for i in range(2, N + 1): # Update the value of dp[i][0] dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 2][1] + dp[i - 2][2]) % MOD # Update the value of dp[i][1] dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD # Update the value of dp[i][2] dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD # Return the number of ways as # the value of dp[N][0] return int(dp[N][0])# Driver CodeN = 3print(numTilings(N))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{static int MOD = 1000000007;// Function to find the total number// of ways to tile a 2*N board using// the given types of tilestatic int numTilings(int N){ // If N is less than 3 if (N < 3) { return N; } // Store all dp-states int [,]dp = new int[N+1,3]; // Base Case dp[0,0] = dp[1,0] = 1; dp[1,1] = dp[1,2] = 1; // Traverse the range [2, N] for (int i = 2; i <= N; i++) { // Update the value of dp[i,0] dp[i,0] = (dp[i - 1,0] + dp[i - 2,0] + dp[i - 2,1] + dp[i - 2,2]) % MOD; // Update the value of dp[i,1] dp[i,1] = (dp[i - 1,0] + dp[i - 1,2]) % MOD; // Update the value of dp[i,2] dp[i,2] = (dp[i - 1,0] + dp[i - 1,1]) % MOD; } // Return the number of ways as // the value of dp[N,0] return dp[N,0];}// Driver Codepublic static void Main(){ int N = 3; Console.Write(numTilings(N));}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approache9 + 7; // Function to find the total number // of ways to tile a 2*N board using // the given types of tile const MOD = 1e9 + 7; function numTilings(N) { // If N is less than 3 if (N < 3) { return N; } // Store all dp-states let dp = Array(N + 1).fill().map(() => Array(3).fill(0)) // Base Case dp[0][0] = dp[1][0] = 1; dp[1][1] = dp[1][2] = 1; // Traverse the range [2, N] for (let i = 2; i <= N; i++) { // Update the value of dp[i][0] dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 2][1] + dp[i - 2][2]) % MOD; // Update the value of dp[i][1] dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // Update the value of dp[i][2] dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; } // Return the number of ways as // the value of dp[N][0] return dp[N][0]; } // Driver Code let N = 3; document.write(numTilings(N));// This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Easy Dp Algorithm Using Extra O(n) space.
C++
#include<bits/stdc++.h>#include<iostream>#define ll long longll mod=1e9+7;using namespace std;void the_solver(int n){ vector<ll>dp(n+1,0); dp[0]=1; dp[1]=1;dp[2]=2;dp[3]=5; if(n<=3){ cout<<dp[n]<<endl; return; } for(int i=4;i<=n;i++){ dp[i]=2*(dp[i-1])+dp[i-3]; dp[i]%=mod; } cout<<dp[n]<<endl; return;}signed main(){ int n=3; the_solver(n); return 0;} |
Java
//Java code for the above approachimport java.util.*;class Main { static final long mod = 1000000000L + 7; // Function to solve problem static void theSolver(int n) { // Create an array of size n+1 to store the dp values long[] dp = new long[n + 1]; dp[0] = 1; dp[1] = 1; dp[2] = 2; dp[3] = 5; // If n is less than or equal to 3 if (n <= 3) { System.out.println(dp[n]); return; } // Iterate through the array for (int i = 4; i <= n; i++) { dp[i] = 2 * (dp[i - 1]) + dp[i - 3]; dp[i] %= mod; } System.out.println(dp[n]); return; } public static void main(String[] args) { int n = 3; theSolver(n); }} |
Python3
mod = int(1e9+7)def the_solver(n): dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 dp[2] = 2 dp[3] = 5 if n <= 3: print(dp[n]) return for i in range(4, n + 1): dp[i] = 2 * dp[i - 1] + dp[i - 3] dp[i] %= mod print(dp[n]) returnn = 3the_solver(n)# This codez is contributed by lokeshpotta20. |
Javascript
function the_solver(n){ let dp=new Array(n).fill(0); dp[0]=1; dp[1]=1; dp[2]=2; dp[3]=5; if(n<=3) { document.write(dp[n]); return; } for(let i=4;i<=n;i++){ dp[i]=2*(dp[i-1])+dp[i-3]; dp[i]%=mod; } document.write(dp[n]); return;} let n=3; the_solver(n); |
C#
using System;using System.Linq;using System.Collections.Generic;class GFG { static int mod=1000000007; static void the_solver(int n) { int[] dp=new int[n+1]; for(int i=0; i<n+1; i++) dp[i]=0; dp[0]=1; dp[1]=1; dp[2]=2; dp[3]=5; if(n<=3){ Console.WriteLine(dp[n]); return; } for(int i=4;i<=n;i++) { dp[i]=2*(dp[i-1])+dp[i-3]; dp[i]%=mod; } Console.WriteLine(dp[n]); return; } static public void Main() { int n=3; the_solver(n); } } |
Output
5
Time Complexity: O(N).
Auxiliary Space: O(N).
Recursion Algorithm:
Types of domino and tromino
When no spaces
T1: Vertical domino
T2: Horizaontal domino
T3: 2 different types of Tromino
When there is a space
T4: Horizontal domino
T5/T6: 2 different types of Tromino depending upon the space
These steps describe a recursive algorithm to count the number of ways to tile a 2 x n grid using the given set of tiles, with T1 through T6 representing the different types of tiles.
No Previous Space Present:
- Place T1 and move to i+1: solve(i+1, previousGap=false)
- Place T2 in pair and move to i+2: solve(i+2, previousGap=false)
- Place either T3 or T4 (consider both cases) and move to i+2 with gap at i+1th column: 2*solve(i+2, previousGap=true)
Previous Space Present:
- Place T5 or T6 & fill previous gap (consider only 1 because depending on current configuration, only 1 grid out of them will fit) and move to i+1 with no previous gaps remaining: solve(i+1, previousGap=false)
- Place T2 & fill previous gap and move to i+1 with gap present in ith column: solve(i+1, previousGap=true)
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const long long MOD = 1e9 + 7;// Function to find the total number// of ways to tile a 2*N board using// the given types of tileint func(int idx, int space, int n){ if (idx > n + 1) { return 0; } if (idx == n + 1) { if (space == true) { return 0; } return 1; } // Recursive case: try placing a tile horizontally or // vertically int cnt = 0; if (space == false) { cnt += func(idx + 1, false, n); cnt += func(idx + 2, false, n); cnt += 2 * func(idx + 2, true, n); } else { cnt += func(idx + 1, false, n); cnt += func(idx + 1, true, n); } return cnt % MOD;}// Wrapper function to call func with initial valuesint numTilings(int N) { return func(1, false, N); }// Driver Codeint main(){ int N = 3; cout << numTilings(N); return 0;} |
Java
import java.io.*;import java.util.*;// "static void main" must be defined in a public class.// java program for the above approachpublic class Main { static int MOD = 1000000007; // Function to find the total number // of ways to tile a 2*N board using // the given types of tile public static int func(int idx, boolean space, int n) { if (idx > n + 1) { return 0; } if (idx == n + 1) { if (space == true) { return 0; } return 1; } int cnt = 0; if (space == false) { cnt += func(idx + 1, false, n); cnt += func(idx + 2, false, n); cnt += 2 * func(idx + 2, true, n); } else { cnt += func(idx + 1, false, n); cnt += func(idx + 1, true, n); } return cnt % MOD; } public static int numTilings(int N){ return func(1, false, N); } public static void main(String[] args) { int N = 3; System.out.println(numTilings(N)); }}// The code is contributed by Nidhi goel. |
Python3
# Python program for the above approachMOD = int(1e9 + 7)# Function to find the total number# of ways to tile a 2*N board using# the given types of tiledef func(idx, space, n): if idx > n + 1: return 0 if idx == n + 1: if space == True: return 0 return 1 cnt = 0 if space == False: cnt += func(idx + 1, False, n) cnt += func(idx + 2, False, n) cnt += 2 * func(idx + 2, True, n) else: cnt += func(idx + 1, False, n) cnt += func(idx + 1, True, n) return cnt % MODdef numTilings(N): return func(1, False, N)# Driver Codeif __name__ == "__main__": N = 3 print(numTilings(N))# This code is contributed by codebraxnzt |
Javascript
const MOD = 1e9 + 7;// Function to find the total number// of ways to tile a 2*N board using// the given types of tilefunction func(idx, space, n) {if (idx > n + 1) {return 0;}if (idx === n + 1) { if (space === true) { return 0; } return 1;}let cnt = 0;if (space === false) { cnt += func(idx + 1, false, n); cnt += func(idx + 2, false, n); cnt += 2 * func(idx + 2, true, n);} else { cnt += func(idx + 1, false, n); cnt += func(idx + 1, true, n);}return cnt % MOD;}function numTilings(N) {return func(1, false, N);}// Driver Codeconst N = 3;console.log(numTilings(N)); |
C#
using System;public class GFG{static int MOD = 1000000007; // Function to find the total number// of ways to tile a 2*N board using// the given types of tilepublic static int Func(int idx, bool space, int n){ if (idx > n + 1) { return 0; } if (idx == n + 1) { if (space == true) { return 0; } return 1; } int cnt = 0; if (space == false) { cnt += Func(idx + 1, false, n); cnt += Func(idx + 2, false, n); cnt += 2 * Func(idx + 2, true, n); } else { cnt += Func(idx + 1, false, n); cnt += Func(idx + 1, true, n); } return cnt % MOD;}public static int NumTilings(int N){ return Func(1, false, N);}public static void Main(string[] args){ int N = 3; Console.WriteLine(NumTilings(N));}} |
Output
5
Time Complexity: O(3N) where N is the given number of columns of grid. We are branching out a max of 3 recursive calls each time and N such states giving total time complexity of O(3N)
Auxiliary Space: O(N), required for the recursive stack.
Memoization:
By analyzing the recursion tree from the previous approach, we can see that many redundant
calls were made to the same function state. This is because the answer for a given set of parameters,
i and space, will always be the same. To avoid repeating these calculations, we can use dynamic
programming and store the result in a dp array. The dp[i][space] entry represents the number of
ways to tile a grid starting from the ith column and whether the previous column had a spaceor not.
If we find that dp[i][space] has already been calculated, we can simply return the stored result instead
of repeating the calculation.
We can cache the result of recursion to convert into a dp solution
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const long long MOD = 1e9 + 7;// Function to find the total number// of ways to tile a 2*N board using// the given types of tilelong long int func(long long int idx, bool space, int n, vector<vector<int> >& dp){ if (idx > n + 1) { return 0; } if (idx == n + 1) { if (space == true) { return 0; } return 1; } if (dp[idx][space] != -1) { return dp[idx][space]; } long long int cnt = 0; if (space == false) { cnt += func(idx + 1, false, n, dp); cnt += func(idx + 2, false, n, dp); cnt += 2 * func(idx + 2, true, n, dp); } else { cnt += func(idx + 1, false, n, dp); cnt += func(idx + 1, true, n, dp); } return dp[idx][space] = cnt % MOD;}int numTilings(int N){ vector<vector<int> > dp(N + 2, vector<int>(3, -1)); return func(1, false, N, dp);}// Driver Codeint main(){ int N = 3; cout << numTilings(N); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;public class GFG { static final long MOD = (long) 1e9 + 7; // Function to find the total number // of ways to tile a 2*N board using // the given types of tile static long func(int idx, boolean space, int n, List<List<Long>> dp) { if (idx > n + 1) { return 0; } if (idx == n + 1) { if (space == true) { return 0; } return 1; } if (dp.get(idx).get(space ? 1 : 0) != -1) { return dp.get(idx).get(space ? 1 : 0); } long cnt = 0; if (!space) { cnt += func(idx + 1, false, n, dp); cnt += func(idx + 2, false, n, dp); cnt += 2 * func(idx + 2, true, n, dp); } else { cnt += func(idx + 1, false, n, dp); cnt += func(idx + 1, true, n, dp); } dp.get(idx).set(space ? 1 : 0, cnt % MOD); return dp.get(idx).get(space ? 1 : 0); } static int numTilings(int N) { List<List<Long>> dp = new ArrayList<>(); for (int i = 0; i <= N + 1; i++) { dp.add(new ArrayList<>(Arrays.asList(-1L, -1L))); } return (int) func(1, false, N, dp); } // Driver Code public static void main(String[] args) { int N = 3; System.out.println(numTilings(N)); }} |
C#
using System;public class Program { const long MOD = 1000000007; // Function to find the total number // of ways to tile a 2*N board using // the given types of tile public static long Func(int idx, bool space, int n, long[][] dp) { if (idx > n + 1) { return 0; } if (idx == n + 1) { if (space == true) { return 0; } return 1; } if (dp[idx][space ? 1 : 0] != -1) { return dp[idx][space ? 1 : 0]; } long cnt = 0; if (!space) { cnt += Func(idx + 1, false, n, dp); cnt += Func(idx + 2, false, n, dp); cnt += 2 * Func(idx + 2, true, n, dp); } else { cnt += Func(idx + 1, false, n, dp); cnt += Func(idx + 1, true, n, dp); } return dp[idx][space ? 1 : 0] = cnt % MOD; } public static int NumTilings(int N) { long[][] dp = new long[N + 2][]; for (int i = 0; i < dp.Length; i++) { dp[i] = new long[3]; for (int j = 0; j < dp[i].Length; j++) { dp[i][j] = -1; } } return (int)Func(1, false, N, dp); } public static void Main() { int N = 3; Console.WriteLine(NumTilings(N)); }}// This code is contributed by user_dtewbxkn77n |
Python3
def numTilings(N): MOD = 10**9 + 7 # the modulo value def func(idx, space, n, dp): # base case 1: when we exceed the column limit, there is no way to tile further if idx > n + 1: return 0 # base case 2: when we reach the end of the column, we have completed the tiling if idx == n + 1: if space == True: return 0 # if there is a space left, the tiling is not valid return 1 # if there is no space left, the tiling is valid and we return 1 # if we have already computed the result for this position and state, we return it if dp[idx][1 if space else 0] != -1: return dp[idx][1 if space else 0] cnt = 0 # variable to count the number of valid tilings if not space: # if there is no space to fill cnt += func(idx + 1, False, n, dp) # case 1: place a vertical tile at the current position cnt += func(idx + 2, False, n, dp) # case 2: place two horizontal tiles at the current position cnt += 2 * func(idx + 2, True, n, dp) # case 3: place two vertical tiles at the current position, leaving a space in between else: # if there is a space to fill cnt += func(idx + 1, False, n, dp) # case 1: place a vertical tile at the current position to fill the space cnt += func(idx + 1, True, n, dp) # case 2: leave the space empty # memoize the result for this position and state dp[idx][1 if space else 0] = cnt % MOD return dp[idx][1 if space else 0] # initialize the memoization table dp = [[-1, -1] for _ in range(N + 2)] # call the recursive function to find the number of valid tilings return func(1, False, N, dp)# Driver CodeN = 3print(numTilings(N)) |
Output
5
Time Complexity : O(N) where N is the given number of columns of grid
Auxiliary Space : O(N), required for recursive stack and maintaining dp
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
