I couldn’t understand anything whatever the mentor explained in the lecture. Please explain me the question first and then the solution of it in detail. Please send the code also.
Tiling problem in recursion
We have to find a recursive relation to tile a floor of size 4 x N given tile size is 1 x 4
When you keep the tile vertically, number of ways of tiling the remaining floor is f(n-1) as n-1 is the remaining width.
When you keep the tiles horizontally, number of ways of tiling remaining floor is f(n-4).
So total number of ways pf tiling is the sum of both.
You can refer this Please help me to understand the question
Also watch the video again. It is clearly explained there.
// Recursive function to find number of ways to fill a n x 4 matrix
// with 1 x 4 tiles
int totalWays(int n)
{
if (n < 1)
return 0;//Because tiling not possible
if (n < 4)
return 1;//Because now you have only 1 way to tile and that is to tile vertically
if (n == 4)
return 2; //Because now you have 2 ways- either tile all vertically or tile all horizontally
// combine results of placing a tile horizontally and
// placing 4 tiles vertically
return totalWays(n - 1) + totalWays(n - 4);
}
Sir I couldn’t understand how f(n-1) and f(n-4) are the number of ways when the tile is placed horizontally and vertically respectively?
It’s really very confusing. I am very sorry to say this but Prateek Bhaiya has explained the concept in such a way that only the intelligent student can understand, not a below-average guy like me.
Please help me.