How to approach this question

#1

Given a floor of size n x m. Find the number of ways to tile the floor with tiles of size 1 x m . A tile can either be placed horizontally or vertically.

#2

Imagine you have a floor of size n × m and you are given tiles of size 1× m.
Now you can either place the tiles vertically. Where a tile can be either place vertically,meaning it will only occupy a cell of width 1 and a complete height of M

there are 3 possibilities:

n>m - here you can place a tile vertically(left with n-m,m) as well as horizontally(left with n-1,m).
n==m then there are always 2 ways - horizontally or vertically.
n<m here you have only 1 choice,that is to place tile horizontally, so 1 way only.
Also mere recursion won’t help in passing all test cases, dynamic programming
image

another example:
image
you can see this:

#3

Thanks… for this …

1 Like