f(n) = f(n-1) + f(n-4)
I couldn’t understand the above recursion condition. please explain _/_.
Didn't understand the recursion condition
hi @ankit-c11
there are 2 ways to place the tile, vertically and horizontally.
if we place a tile vertically, it means that if the total length of floor is n, 1 unit will be occupied. That leaves us with a subproblem of covering (n-1) tiles.
If we place a tile horizontally, we will actually have to place 3 more tiles on top of it. And the total length of floor occupied will be 4, which leaves us with a subproblem of covering (n-4) tiles.
So, we have 2 possibilities, and since we can use only one of them, we have to ADD the answer returned by both these scenarios.
Hence the recurrence relation is f(n) = f(n-1) + f(n-4)
base cases will be
n<=0 return 0
n == 1 return 1
n == 4 return 2
Got it… Thanks a lot… Mam could you please provide some references to practice more of such problems _/_.