N = no of rows, M = no of columns
if(N == M) -> then return 2 as there only two ways either horizontal or vertical both are possible.
if(N < M) -> then return 1 as there will be only 1 horizontal way of stacking up the tiles in one way i.e. horizontal is possible.
if(N > M) then also return 1 as we can stack up in one way only
so without recursion problem can be solved
Am I thinking correctly ?
Please help
Without recursion problem can be solved?
No, you are thinking about it in the wrong way. Think of it in this way. How would tile up your nth column. You could either tile 1 tile vertically and your nth column gets stacked. An other way to tile up your nth column is to stack m tiles horizontally. That means, if f(x) denotes the number of ways to tile x * m tile with tiles of size 1 * m, then f(n) = f(n - 1) + f(n - m). Think of the base cases yourself.
I understood what you are trying to say but in question the matrix is n*m so n = no of rows and m = no of columns but what you are explaining you are taking n as no of columns and m as no of rows
Ohh. I must have read it ulta. Anyways, I’m sure you’ve got my point
but then it should not be f(n - 1) + f(n - m) as n is no of rows not column right? it should be then what I have asked before
it will still be this only since now I can modify the definition of my f function to be number of ways to tile i * m board using tiles of size 1 * m. The point is, it doesn’t really matter if it’s rows or columns. You will get it very clearly once you draw a diagram for the same.
Print answer for every test case in a new line modulo 10^9+7. how to do that ? I am getting TLE in 4 test cases my base case is if(n < m) return 1;
and rec case is f(n - 1) + f(n - m)
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.