Introduction: Welcome back, dear reader. So, how is it going? Are you enjoying dynamic programming? We hope you are. So, let's discuss this problem called TILING WITH 2X1 TILES. We recommend you to watch the TILING WITH 2X1 TILES video to understand the problem completely. Let's discuss the problem ourselves too. Look at the diagram given below:
Prev Next
Tiling with 2x1 tiles
Problem Discussion :
We are given a floor whose width is 2m and its length is n meters. We are also given infinite tiles of size 2x1 i.e the width of the tiles is also 2 meters but the length of each tile is 1m. We have to find the total number of ways in which we can tile up the entire floor using these tiles. For instance: Let us say that n=3 i.e the floor has a length of 3m. Then it can be tiled up in the ways as shown:
So, now you have understood the question. We recommend you try this problem yourself and try to find out the solution.
Hint: Relate it to the source-destination problems that we have been solving so far.
Approach:
We will approach this problem differently. We will think about it as we used to think about the solution to our problem in recursion. We will break down the entire solution into a recursive relation and then try to solve it using dynamic programming. So, let us first break this into our classical source-destination problem. Look at the diagram given below:
We have already given you the hint that this problem can be solved by thinking of it as a source-destination problem, a lot of which we have already solved. Now, in this problem,
the source is our completely untiled floor and the destination is our completely tiled floor. Note that all the completely tiled floors will be our destination. It doesn't matter how they are tiled. They should just be completely tiled.of source-destination problem we try to find out all the initial points to where we can go from our starting point. What do we mean by this? Look at the diagram given below which depicts the solution diagram for any general source-destination problem:
We have a source and we have to reach our destination. Let us say we know that we can go to 3 points/spots directly from the source. These are i1, i2, i3. Now from each of these points, we have several paths to go to our destination. If we want to find the number of paths then we know that source to i1 is 1 path. If we know the paths from i1 to the destination we can count the total number of paths in the same way by putting 1 in front of the total paths from i2 to the destination and from i3 to the destination. This is a general approach that we have followed in the source-destination problems. The paths from i1,i2, and i3 are given to us by recursion (remember the faith part? We did this in many problems like PRINT MAZE PATHS and PRINT STAIR PATHS, etc. You may revisit these questions if you want to.) You may refer to the solution video to understand the concept of the source-destination diagram.
Now, let us see how this approach is valid for our question. Have a look at the diagram given below:
When we are at our source i.e. completely untiled floor, we can go to 2 intermediate destinations directly from here i.e. we can place a tile on this floor in 2 ways. We can either place our tile vertically or we can place our tile horizontally. So, after reaching these intermediate destinations, we can trust that we will get the paths/ways of tiling the floor from each intermediate destination. This is the similarity between our problem and the source-destination problem.
Now, let us approach our problem and try to find a recurrence relation and then reduce the recurrence relation to our Dynamic Programming solution. Look at the diagram shown above again (fig-5). If we place our tile vertically we now have to find the number of ways to tile up a floor of length (n-1) whereas earlier our problem was to tile up the floor of length n. So, we have reduced our large problem into a smaller problem of the same kind. You know what this is, right? This is recursion. So, We can express this as shown in the diagram below:
The diagram above shows the left call (that was made in fig-5) in which we placed a tile vertically on the floor. So, after placing this tile vertically, we have actually one part of the floor tiled and the other part as untitled. So, the part which is already tiled will not take part in further tiling. So, we can simply remove that part from our question floor and our question reduces to a floor of smaller length i.e. a floor of length n-1. This is represented in the form of recursive function calls in the diagram above i.e. f(n) and f(n-1).
Now, let us try to solve the other part. Here, we have placed a tile horizontally (as shown in the fig-5) So, now let us try to reduce this into a recursive case too. Look at the diagram given below:
We have to find the number of ways in which we can tile floor, right? So dear reader, if we remove the space where only 1 tile can fit then the floor becomes a floor of length n-2. But, how can we remove it if we don't know the number of ways in which that part of the floor can be tiled?
Well, we do know the number of ways in which it can be tiled. It has a space of keeping only 1 tile that is too horizontally so, that is the only way in which it can be tiled. Since now we know the number of ways in which it can be tiled, we can simply remove it. The conclusion is that the number of ways in which that weird shape can be tiled is the same as the number of ways in which a floor of length n-2 can be tiled. So now, we have to calculate only the number of ways in which the floor of length n-2 can be tiled. This is the small version of the same problem and so we can write the recurrence relation as:
f(n)=f(n-1)+f(n-2)
You may refer to the solution video (2:41-12:05) to understand the above section of the article and establish the recurrence relation. Now, we will convert the above approach into dynamic problem-solving.
Converting Our Approach to DP :
Storage and Meaning: We will make an array dp of size=n+1 where n is the length of the floor. We will also fill in some of the values as the base cases. Look at the diagram given below:
We have created an array dp[n+1]. First of all what does an element of this array represent? An element of this array at ith index represents the number of ways in which the floor of length i can be tiled. So, we have kep 0 at index 0 of the array as there is no way we can tile a floor of index=0. Similarly a floor of length 1 can be tied only in 1 way and a floor of length 2 can be tied in 2 ways as shown below:
Our problem size increases with the length of the floor. Since i represents the length of the floor therefore we can say that the size of our problem increases with increment in i. Therefore the direction of solving is from 0 to in the dp[n+1] array.
Traverse and solve:Since we have already formulated the recurrence relation, that is exactly what we are going to use to solve our problem. We can place our tile vertically, reducing the floor size to length=i-1 and vertically reducing the size of floor to i-2 (since i represents the current size of the floor). So, we are going to traverse the array and at dp[i] we will store dp[i-1]+dp[i-2].
Now, since we know the entire procedure, let us try to code the solution.
Pseudo Code:
- Storage and Meaning: We will make a dp array of size n+1 where n is the length of the floor. Here each element inside the array dp i.e. dp[i] will represent the number of ways in which a floor of size 2xi can be tiled up.
- The Direction of Solving: Since each element in the array defines the number of ways in which a floor of length "i" can be tiled, a floor of length 0 can not be tiled and a floor of length 1 will be tiled in only one way and so on. So, these are small problems and the large problem is finding the number of ways in which we can tile up a floor of length n. So, the direction of solving is from i=0 to n.
- Traverse and Solve: The third and final step in dynamic programming solutions is to traverse and solve. Here we will solve by adding the previous two values to dp[i] and moving forward which means that we will be having dp[i]=dp[i-1] + dp[i-2]. Why? Think about this!!!!!!
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn=new Scanner(System.in);
int n=scn.nextInt();
int[] dp=new int[n+1];
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3;i< dp.length;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
System.out.println(dp[n]);
}
}
java;
true";
Analysis
Time Complexity :
The time complexity of this method is O(n) where n is the length of the floor because we are just traversing an array of length n+1.
SPACE COMPLEXITY :
The space complexity of the above procedure is O(n) as we have created a dp array of size n+1.
Dear reader, we hope that you have understood this problem and also understood how a problem can be understood in recursion and converted into a Dynamic Programming problem.
Suggestions :
Here are some suggestions from our side that you don't want to miss:
- First of all, congratulations to you buddy! You have already solved a lot of problems on Dynamic Programming and by solving these questions in order, you are learning a lot. So, we suggest that you should not think of yourself as less than anyone else. You know less because you are in a learning procedure right now. You just have to keep working hard.
- We suggest you take a look at the code of this problem once again. So, do you get something from this? Yes, it is almost the same as fibonacci sequence code.
This means, since you are asked only about the total number of ways of tiling, you can avoid using the dp array also and your space complexity reduces to O(1). Try this yourself!!! Till then, Happy Coding!!!
