# Tiling Problem

## Tiling Problem

In the tiling problem, we have to find the number of ways to fill a board. The problem has a similar solution as the Fibonacci number using dynamic programming. In this article, we have a C++ solution with an explanation. ## Tiling Problem Description

We are given a land of 2*n. We are given infinite supply of 2*1 tiles. We can place these tiles either horizontally or vertically. Find the number of ways to cover the land.

Input:

• First line contains integer n – The width of land.

Output:

• Required number of ways

## Tiling Problem Solution Explanation

Hint – This problem has similar solution used to find nth Fibonacci number using dynamic programming.

### Solution (Top Down):

To build a top down solution we must follow the following steps –

• Break Down the Problem –Let’s suppose we have a function F(x) that outputs number of ways to fill a land of 2*x dimension. Then –

F(x) = F(x-1) + F(x-2)

ie Place a vertical tile at nth Position + Place vertical tile at (n-1)th position.

• Find the base case – Base case is the solution of smallest known problem. In this problem we know that F(1) = 1 (We can have only 1 file in vertical orientation) & F(2) = 2 { 2 tiles in vertical orientation or 2 tiles in horizontal orientation}.
• Check for optimal substructure and overlapping sub problems – It is easy to see that the problem can be broken down into smaller problems. {Same as Fibonacci numbers}.

Time & Space Complexity – O(n) ### Code

#include<bits/stdc++.h>
using namespace std;
int dp;
int f(int n)
{
if(n<=2)
return n;
if(dp[n]!=-1)
return dp[n];
return dp[n] = f(n1) + f(n2);
}
int main()
{
memset(dp,-1,sizeof dp);
int n;
cin>>n;
cout<<f(n)<<endl;
}

`33`

### Bottom up Solution

Here we create a dp array of length n+1. And use similar transition as above.

Time & Space Complexity – O(n)

### Code

#include <bits/stdc++.h>
using namespace std;
int dp;
int f(int n)
{
dp = 1;
dp = 2;
for (int i = 3i <= ni++)
dp[i] = dp[i – 1] + dp[i – 2];
return dp[n];
}
int main()
{
int n;
cin >> n;
cout << f(n) << endl;
}

`33`