__Introduction__

__Introduction__

Some questions can be solved very simply by identifying a pattern being followed and using the concept of __Fibonacci numbers. __

Fibonacci numbers follow the following sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…..

The recurrence relation for the sequence is given by

The Fibonacci pattern can be observed in nature, and it is often considered a fundamental problem of__ dynamic programming. __

This is because instead of calculating the results, again and again, we store the results of the subproblem, which helps prevent recalculations.

For example, let **N = 5.**

The recursion tree for this would be:

Let us look at one such problem that is equally important from an interview perspective and primarily based on identifying the pattern.

__Problem Statement:__

__Problem Statement:__Consider a board of size* 2 * N *and tiles of size “

*”. You have to count*

**2 * 1***the number of ways in which tiling of this board is possible*. You may place the tile vertically or horizontally, as per your choice.

Let us understand the problem with the help of a few examples:

__Example__

__Example__

**N = 4**

The tiling of this board is possible in * 3* different ways. Let us see how:

- All
bricks can be placed**4***vertically.*

- All
bricks can be placed**4***horizontally.*

bricks can be placed**2***horizontally*and**2***vertically*.

2.* N = 3*

The tiling of this board is possible in * 2* different ways. Let us see how:

- All
bricks can be placed**3***vertically.*

bricks can be placed**2***horizontally and*brick**1***vertically.*

3. **N = 5**

The tiling of this board is possible in * 3* different ways. Let us see how:

- All
bricks can be placed**5***vertically.*

bricks can be placed**4***horizontally*and**1***vertically in***2***different ways.*

bricks can be placed**2***horizontally*and**3***vertically in***2***different ways.*

Now, let us solve this Tiling problem using * recursion*, and then we will see how and why it can be optimized using Dynamic Programming:

__Recursion__

__Recursion__

We will solve this problem using recursion. We will start to tile the board from the last column, i.e.; we will first tile the * N^{th}* column, then

*column, and so on.*

**(N-1)**^{th}There are * 2* cases possible:

- If we place the tile vertically, the problem will be converted into a sub-problem of tiling a board of size
**2 * (N - 1).** - If we place the tile horizontally,
tiles will be required to cover the**2**and**N**^{th}column, and now the problem will be converted into a sub-problem of tiling a board of size**(N - 1)**^{th}**2 * (N - 2).**

Thus, if * countOfWays(N) *denotes the number of ways to tile a board of size

*, then,*

**2 * N**If you observe, this pattern follows the *Fibonacci Sequence. *Hence its implementation is also the same.

### Implementation

__Program__

__Program__

```
/* C++ program to count the number of ways to place 2 * 1 size tiles on a 2 * n size board using recursion.*/
#include <iostream>
using namespace std;
// Function to calculate the total number of possible ways of tiling a board.
int numOfWays(int n)
{
// Base case.
if (n == 0 || n == 1)
return n;
return numOfWays(n - 1) + numOfWays(n - 2);
}
int main()
{
int n;
// Taking user input.
cout << "Enter the value of N: ";
cin >> n;
// Calling the function to predict the output.
cout << "The total number of possible ways to place the tiles on the board are " << numOfWays(n);
return 0;
}
```

__Input:__

__Input:__

`Enter the value of N: 5`

__Output:__

__Output:__

`The total number of possible ways to place the tiles on the board is 5.`

**Time Complexity**

**Time Complexity**

The time complexity of this technique is exponential and is given by * O(2^{N}), *where

*is the size of the board.*

**2 * N**The function uses __Recursion__, and in the worst case, it makes * 2* calls for every

*. Thus, the time complexity is*

**N***.*

**O(2**^{N})**Space Complexity**

**Space Complexity**

The space complexity is* O(N)*, where ‘

*’ is the length of the board.*

**N**In any case, there will be a maximum of* ‘N’* function calls that will occupy

*space of the recursion call stack. Hence*

**O(N)***the space complexity is given by*

**,***.*

**O(N)**Now, we will see why and how the solution can be optimized using DP.

Read More - __Time Complexity of Sorting Algorithms__