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.
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
// function to count the total number of ways
// table to store values
// of subproblems
count = 0;
// Fill the table upto value n
i = 1; i< = n; i++)
// recurrence relation
(i > m)
count[i] = count[i-1] + count[i-m];
// base cases
(i < m)
count[i] = 1;
// i = = m
count[i] = 2;
// required number of ways
// Driver program to test above
n = 7, m = 4;
"Number of ways = "
<< countWays(n, m);
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