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++
// 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 waysint 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 and for i = m = 1 else if (i < m || i == 1) count[i] = 1; // i = = m else count[i] = 2; } // required number of ways return count[n];}// Driver program to test aboveint main(){ int n = 7, m = 4; cout << "Number of ways = " << countWays(n, m); return 0;} |
Java
// Java implementation to count number// of ways to tile a floor of size// n x m using 1 x m tilesimport java.io.*;class GFG { // function to count the total number of ways static int countWays(int n, int m) { // table to store values // of subproblems int count[] = new int[n + 1]; count[0] = 0; // Fill the table upto value n int i; for (i = 1; i <= n; i++) { // recurrence relation if (i > m) count[i] = count[i - 1] + count[i - m]; // base cases else if (i < m || i == 1) count[i] = 1; // i = = m else count[i] = 2; } // required number of ways return count[n]; } // Driver program public static void main(String[] args) { int n = 7; int m = 4; System.out.println("Number of ways = " + countWays(n, m)); }}// This code is contributed by vt_m. |
Python3
# Python implementation to# count number of ways to # tile a floor of size n x m# using 1 x m tilesdef countWays(n, m): # table to store values # of subproblems count =[] for i in range(n + 2): count.append(0) count[0] = 0 # Fill the table upto value n for i in range(1, n + 1): # recurrence relation if (i > m): count[i] = count[i-1] + count[i-m] # base cases elif (i < m or i == 1): count[i] = 1 # i = = m else: count[i] = 2 # required number of ways return count[n]# Driver coden = 7m = 4print("Number of ways = ", countWays(n, m))# This code is contributed# by Anant Agarwal. |
C#
// C# implementation to count number// of ways to tile a floor of size// n x m using 1 x m tilesusing System;class GFG { // function to count the total // number of ways static int countWays(int n, int m) { // table to store values // of subproblems int[] count = new int[n + 1]; count[0] = 0; // Fill the table upto value n int i; for (i = 1; i <= n; i++) { // recurrence relation if (i > m) count[i] = count[i - 1] + count[i - m]; // base cases and i = m = 1 else if (i < m || i == 1) count[i] = 1; // i = = m else count[i] = 2; } // required number of ways return count[n]; } // Driver program public static void Main() { int n = 7; int m = 4; Console.Write("Number of ways = " + countWays(n, m)); }}// This code is contributed by parashar. |
PHP
<?php// PHP 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 waysfunction countWays($n, $m){ // table to store values // of subproblems $count[0] = 0; // Fill the table // upto value n for ($i = 1; $i <= $n; $i++) { // recurrence relation if ($i > $m) $count[$i] = $count[$i - 1] + $count[$i - $m]; // base cases else if ($i < $m or $i == 1) $count[$i] = 1; // i = = m else $count[$i] = 2; } // required number of ways return $count[$n];} // Driver Code $n = 7; $m = 4; echo "Number of ways = ", countWays($n, $m);// This code is contributed by ajit?> |
Javascript
<script> // Javascript 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 function countWays(n, m) { // table to store values // of subproblems let count = new Array(n + 1); count[0] = 0; // Fill the table upto value n let i; for (i = 1; i <= n; i++) { // recurrence relation if (i > m) count[i] = count[i - 1] + count[i - m]; // base cases and i = m = 1 else if (i < m || i == 1) count[i] = 1; // i = = m else count[i] = 2; } // required number of ways return count[n]; } let n = 7; let m = 4; document.write("Number of ways = " + countWays(n, m));// This code is contributed by rameshtravel07.</script> |
Output:
Number of ways = 5
Time Complexity: O(n)
Auxiliary Space: O(n)
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
