Tilling Problem II

#1

In this question modulo(10^9+7) what does it mean??
and when row and columns are not same then answer can be only 1 otherwise 2. I want to say that ans can be 1 or 2 ??
I have to check only that 1xm is possible or not. If possible then 1 and if mx1 is also possible then answer will be 2.
Am I right ??

#2

modulo(10^9+7) is taken because the answer can be large enough that even exceeds 64 bit value. Answer is not always 1 or 2 as if you tile 1Xm, then you are left with board (n-1)Xm, also if you tile mX1 then you have (n-m)Xm board, hence you need to solve it recursively (or use DP).

#3

Hey I am not able to how to approach for this question please help

#4

Have you solved Tiling Problem I ? If not, solve it first

#5

Ok I got it but how to handle such a large number??

#6

we take modulo(10^9+7) at every step, for more hints you may also refer editorial/solution

#7

Why I am getting TLE ?? https://ide.codingblocks.com/s/231621

#8

@ashwani225 Apply Dynamic Programming here, you can easily apply memoization to optimize this recursive approach.

#9

I have studied only recursion till now and this problem is mentioned in recursion section. Please tell me why I am getting TLE??

#10

@ashwani225 If you see the time complexity for this question is O(2^N) and the constraints are 10^5 for N. So it is not possible, we ave to optimize the solution which can be done using DP

#11

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.