Welcome back, dear reader. Hope you are doing well. So, the previous problem in this section was TILING WITH 2x1 TILES. If you have not solved this question, we recommend you solve it first as it is the basis of this problem. If you are stuck anywhere in the TILING WITH 2X1 PROBLEM, you may refer to its solution video or you may refer to the article on tiling with 2x1 tiles. Now, let's study this problem.
Prev Next
Tiling With Mx1 Tiles
Problem Statement :
This problem states that we have a floor of size nxm where n is the length and m is the width. We also have an infinite number of tiles of size m*1. We have to find the number of ways in which the entire floor can be tiled up. (See fig-1 for reference)
A 2x3 floor is shown in the example above with different ways in which it can be tiled with a 2x1 tile. You may refer to the TILING WITH Mx1 TILES video to understand the question if you have any doubts regarding it.
You are requested to try this question yourself and then come back here to learn in-depth..
Approach :
Algorithm/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 mxi 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 the problem by taking into consideration, placement of tiles vertically as well as horizontally. In general dp[i]=dp[i-1] + dp[i-m]. Why? Think!!!!
Explanation:
We will apply the same thinking procedure for this problem, that we applied in the previous one. 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:
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. Now when we have this kind of source-destination problem we try to find out all the initial points to where we can go from our starting point. We have already discussed this source-destination problem and its diagram in the previous question as well. You may refer to the TILING WITH 2x1 TILES article for this. You may also refer to the solution video for an overview of the source-destination standard diagram.
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-3) in which we placed a tile vertically on the floor. So, after placing this tile vertically, we actually have 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 can be represented in the form of recursive function calls i.e f(m,n) and f(m,n-1) where f(m,n-1) is the floor left after tiling with one tile vertically.
Now, let us try to solve the other part. Here, we have placed a tile horizontally (as shown in the fig-3) So, now let us try to reduce this into a recursive case too. Look at the diagram given below:
The diagram above shows the right call (that was made in fig-3) in which we placed a tile horizontally on the floor. So, after placing this tile horizontally, we have actually one part of the floor as tiled and the other part as untiled. So, the part which is already tiled will not take participation in further tiling. So, we can simply remove that part from our question floor and our question reduces to a smaller floor. But, this is a weirdly shaped floor and we cannot decide what to call it as we can not say that it is the smaller version of the same problem. So, let us try to reduce it to one. Now, if you see (in fig-5) we have put a question mark(?) on the smaller floor we got after removing the tile from the question floor. It has two parts. One part is of the width m-1 and length m. Due to this, there is only 1 way of inserting tiles into this part i.e. insert m-1 tiles horizontally.
We have to find the number of ways in which we can tile the floor, right? So dear reader, if we remove the space where we can tile up the floor in only one way that is we remove the part of mx(m-1) dimensions, we are left with a floor of dimensions mx(n-m). We removed the small part as we knew that there was only 1 way to tile it up and since we know the solution to that part, there is no need to keep it in the question tile. So, the recurrence relation that we finally get is of the form:
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:
- 2. The direction of solving:
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 will also use the base case shown above and traverse from i=0 to i=n to solve our problem.
We have made an array dp of size=n+1 where n is the length of the floor.
Also, look at the base case shown in the figure below:
Now, since we know the entire procedure, let us try to code the solution.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (i < m) {
dp[i] = 1;
} else if (i == m) {
dp[i] = 2;
} else {
dp[i] = dp[i - 1] + dp[i - m];
}
}
System.out.println(dp[n]);
}
}
java;
true";
Dear reader, if you have any doubts regarding the code and the procedure discussed above, you may watch the solution video to clear all your doubts.
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:
- We suggest you revise the previous version of the problem also once again after solving this problem so that your concepts get stronger.
- Also, you can now see how important and interrelated are recursion and Dynamic Programming to each other. So, we suggest you revise it well also. Till then, Happy Coding!!!
