Count the number of ways to tile the floor of size n x m using 1 x m size tiles

Given a floor of size n x m and tiles of size 1 x m. The problem is to count the number of ways to tile the given floor using 1 x m tiles. A tile can either be placed horizontally or vertically.
Both n and m are positive integers and 2 < = m.

Examples:

Input : n = 2, m = 3
Output : 1
Only one combination to place 
two tiles of size 1 x 3 horizontally
on the floor of size 2 x 3. 

Input :  n = 4, m = 4
Output : 2
1st combination:
All tiles are placed horizontally
2nd combination:
All tiles are placed vertically.

This problem is mainly a more generalized approach to the Tiling Problem.
Approach: For a given value of n and m, the number of ways to tile the floor can be obtained from the following relation.

            |  1, 1 < = n < m
 count(n) = |  2, n = m
            | count(n-1) + count(n-m), m < n
             
// C++ implementation to count number of ways to
// tile a floor of size n x m using 1 x m tiles
#include <bits/stdc++.h>
using namespace std;
// function to count the total number of ways
int countWays(int n, int m)
{
    // table to store values
    // of subproblems
    int count[n+1];
    count[0] = 0;
    
    // Fill the table upto value n
    for (int i = 1; i< = n; i++)
    {
        // recurrence relation
        if (i > m)
            count[i] = count[i-1] + count[i-m];
        
        // base cases   
        else if (i < m)   
            count[i] = 1;
        // i = = m   
        else
            count[i] = 2;
    }
    
    // required number of ways
    return count[n];
}
// Driver program to test above
int main()
{
    int n = 7, m = 4;
    cout << "Number of ways = "
         << countWays(n, m);
    return 0;
}

Output:

Number of ways = 5

Time Complexity: O(n)
Auxiliary Space: O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar