Given an integer N, the task is to tile a board of dimensions N * 1 the task is to count the number of ways to tile a board using tiles of dimensions 1 * 1 and 2 * 1.
Examples:
Input: N = 2
Output: 5
Explanation:
Tile the board of size 2 x 1 by placing 1 x 1 tile in a Horizontal way and another 1 x 1 tile in a vertical way.
Tile the board of size 2 x 1 by placing 1 x 1 tile in a vertical way and another 1 x 1 tile in a Horizontal way.
Tile the board of size 2 x 1 by placing 1 x 1 tile in a Horizontal way and another 1 x 1 tile in a Horizontal way.
Tile the board of size 2 x 1 by placing 1 x 1 tile in a vertical way and another 1 x 1 tile in a vertical way.
Tile the board of size 2 x 1 by placing 2 x 1 tile in a horizontal way.
Therefore, the required output is 5.Input: N = 1
Output: 2
Approach: The problem can be solved using Dynamic Programming. The idea is to divide the N x 1 board into smaller boards, then count the ways to tile the smaller boards. Finally, print the total count of ways to tile the N x 1 board. Follow the steps below to solve the problem:
- Following are the three ways to place the first tile:
- Place the 1 x 1 tile vertically.
- Place the 1 x 1 tile horizontally.
- Place the 2 x 1 tile horizontally.
- Therefore, the recurrence relation to solve the problem is as follows:
cntWays(N) = 2 * cntWays(N – 1) + cntWays(N – 2)
- Initialize an array say, dp[], where dp[i] stores the count of ways to tile the i x 1 board.
- Iterate over the range [2, N] and fill the array, dp[] using the tabulation method.
- Finally, print the value of dp[N].
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count the ways to tile N * 1 // board using 1 * 1 and 2 * 1 tiles long countWaysToTileBoard( long N) { // dp[i]: Stores count of ways to tile // i * 1 board using given tiles long dp[N + 1]; // Base Case dp[0] = 1; dp[1] = 2; // Iterate over the range [2, N] for ( int i = 2; i <= N; i++) { // Fill dp[i] using // the recurrence relation dp[i] = (2 * dp[i - 1] + dp[i - 2] ); } cout << dp[N]; } // Driver Code int main() { // Given N long N = 2; // Function Call countWaysToTileBoard(N); return 0; } |
Java
// Java program to implement // the above approach class GFG{ // Function to count the ways to tile N * 1 // board using 1 * 1 and 2 * 1 tiles static void countWaysToTileBoard( int N) { // dp[i]: Stores count of ways to tile // i * 1 board using given tiles int dp[] = new int [N + 1 ]; // Base Case dp[ 0 ] = 1 ; dp[ 1 ] = 2 ; // Iterate over the range [2, N] for ( int i = 2 ; i <= N; i++) { // Fill dp[i] using // the recurrence relation dp[i] = ( 2 * dp[i - 1 ] + dp[i - 2 ]); } System.out.print(dp[N]); } // Driver Code public static void main (String[] args) { // Given N int N = 2 ; // Function Call countWaysToTileBoard(N); } } // This code is contributed by AnkThon |
Python3
# Python3 program to implement # the above approach # Function to count the ways to tile N * 1 # board using 1 * 1 and 2 * 1 tiles def countWaysToTileBoard( N) : # dp[i]: Stores count of ways to tile # i * 1 board using given tiles dp = [ 0 ] * (N + 1 ) # Base Case dp[ 0 ] = 1 dp[ 1 ] = 2 # Iterate over the range [2, N] for i in range ( 2 , N + 1 ) : # Fill dp[i] using # the recurrence relation dp[i] = ( 2 * dp[i - 1 ] + dp[i - 2 ] ) print (dp[N]) # Driver Code if __name__ = = "__main__" : # Given N N = 2 # Function Call countWaysToTileBoard(N) # This code is contributed by jana_sayantan |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to count the ways to tile N * 1 // board using 1 * 1 and 2 * 1 tiles static void countWaysToTileBoard( int N) { // dp[i]: Stores count of ways to tile // i * 1 board using given tiles int []dp = new int [N + 1]; // Base Case dp[0] = 1; dp[1] = 2; // Iterate over the range [2, N] for ( int i = 2; i <= N; i++) { // Fill dp[i] using // the recurrence relation dp[i] = (2 * dp[i - 1] + dp[i - 2]); } Console.Write(dp[N]); } // Driver Code public static void Main(String[] args) { // Given N int N = 2; // Function Call countWaysToTileBoard(N); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for above approach // Function to count the ways to tile N * 1 // board using 1 * 1 and 2 * 1 tiles function countWaysToTileBoard(N) { // dp[i]: Stores count of ways to tile // i * 1 board using given tiles let dp = []; // Base Case dp[0] = 1; dp[1] = 2; // Iterate over the range [2, N] for (let i = 2; i <= N; i++) { // Fill dp[i] using // the recurrence relation dp[i] = (2 * dp[i - 1] + dp[i - 2]); } document.write(dp[N]); } // Driver Code // Given N let N = 2; // Function Call countWaysToTileBoard(N); </script> |
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach: Space Optimization using variables
To optimize the space complexity of the previous code, we can use two variables to keep track of the last two elements of the DP array instead of keeping the entire DP array. This will reduce the space complexity from O(N) to O(1).
Steps that were to follow the above approach:
- The function initializes variables prev1 and prev2 to 1 and 2, respectively.
- The function then enters a loop that iterates over the range [2, N].
- For each i in this range, the function calculates the current element of the DP array using the recurrence relation curr = (2 * prev2 + prev1).
- It then updates the variables prev1 and prev2 to store the last two elements of the DP array for the next iteration.
- After the loop completes, the function returns the value of curr, which corresponds to the count of ways to tile a 1 x N board using 1 x 1 and 2 x 1 tiles.
Below is the code to implement above steps :
C++
#include <bits/stdc++.h> using namespace std; // Function to count the ways to tile N * 1 // board using 1 * 1 and 2 * 1 tiles long countWaysToTileBoard( long N) { // Base Case if (N == 0 || N == 1) { return N + 1; } // Initialize variables to store the last two // elements of the DP array long prev1 = 1, prev2 = 2, curr; // Iterate over the range [2, N] for ( int i = 2; i <= N; i++) { // Calculate the current element of the DP array curr = (2 * prev2 + prev1); // Update the variables to store the last two // elements of the DP array prev1 = prev2; prev2 = curr; } return curr; } // Driver Code int main() { // Given N long N = 2; // Function Call cout << countWaysToTileBoard(N); return 0; } // this code is contributed by bhardwajji |
Java
import java.util.*; public class TilingWays { public static long countWaysToTileBoard( long N) { // Base Case if (N == 0 || N == 1 ) { return N + 1 ; } // Initialize variables to store the last two // elements of the DP array long prev1 = 1 , prev2 = 2 , curr = 0 ; // Iterate over the range [2, N] for ( int i = 2 ; i <= N; i++) { // Calculate the current element of the DP array curr = ( 2 * prev2 + prev1) % (( long ) Math.pow( 10 , 9 ) + 7 ); // Update the variables to store the last two // elements of the DP array prev1 = prev2; prev2 = curr; } return curr; } public static void main(String[] args) { // Given N long N = 2 ; // Function Call System.out.println(countWaysToTileBoard(N)); } } |
Python
def countWaysToTileBoard(N): # Base Case if N = = 0 or N = = 1 : return N + 1 # Initialize variables to store the last two # elements of the DP array prev1, prev2, curr = 1 , 2 , None # Iterate over the range [2, N] for i in range ( 2 , N + 1 ): # Calculate the current element of the DP array curr = 2 * prev2 + prev1 # Update the variables to store the last two # elements of the DP array prev1 = prev2 prev2 = curr return curr # Driver Code if __name__ = = '__main__' : # Given N N = 2 # Function Call print (countWaysToTileBoard(N)) |
Javascript
// Function to count the ways to tile N * 1 // board using 1 * 1 and 2 * 1 tiles function countWaysToTileBoard(N) { // Base Case if (N == 0 || N == 1) { return N + 1; } // Initialize variables to store the last two // elements of the DP array let prev1 = 1, prev2 = 2, curr; // Iterate over the range [2, N] for (let i = 2; i <= N; i++) { // Calculate the current element of the DP array curr = (2 * prev2 + prev1); // Update the variables to store the last two // elements of the DP array prev1 = prev2; prev2 = curr; } return curr; } // Driver Code function main() { // Given N let N = 2; // Function Call console.log(countWaysToTileBoard(N)); } main(); |
C#
using System; public class GFG { // Function to count the ways to tile N * 1 // board using 1 * 1 and 2 * 1 tiles static long CountWaysToTileBoard( long N) { // Base Case if (N == 0 || N == 1) { return N + 1; } // Initialize variables to store the last two // elements of the DP array long prev1 = 1, prev2 = 2, curr = 0; // Iterate over the range [2, N] for ( int i = 2; i <= N; i++) { // Calculate the current element of the DP array curr = (2 * prev2 + prev1); // Update the variables to store the last two // elements of the DP array prev1 = prev2; prev2 = curr; } return curr; } // Driver Code public static void Main() { // Given N long N = 2; // Function Call Console.WriteLine(CountWaysToTileBoard(N)); } } |
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!