# 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++

 `// C++ implementation to count number of ways to ` `// tile a floor of size n x m using 1 x m tiles ` `#include ` ` `  `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; ` ` `  `    ``// 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; ` `} `

## Java

 `// Java implementation to count number ` `// of ways to tile a floor of size ` `// n x m using 1 x m tiles ` `import` `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) ` `                ``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 tiles ` ` `  `def` `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):  ` `            ``count[i] ``=` `1` ` `  `        ``# i = = m  ` `        ``else``: ` `            ``count[i] ``=` `2` `     `  `     `  `    ``# required number of ways ` `    ``return` `count[n] ` ` `  ` `  `# Driver code ` ` `  `n ``=` `7` `m ``=` `4` ` `  `print``(``"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 tiles ` `using` `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; ` ` `  `        ``// 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) ` `                ``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

 ` ``\$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 Code ` `    ``\$n` `= 7; ` `    ``\$m` `= 4; ` `    ``echo` `"Number of ways = "``, countWays(``\$n``, ``\$m``); ` ` `  `// This code is contributed by ajit ` `?> `

Output:

```Number of ways = 5
```

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

## tags:

Dynamic Programming Dynamic Programming