Test cases failing in Tiling-II DP problem

#1

Please help. Here is my solution that I submitted

#2

Help me with the modulo implementation

#3

as ans can be very large so we have to take mod with 10^9+7 after every result

do it like this
return dp[N] = (Tiling(N - 1, M, dp)%mod + Tiling(N - M, M, dp)%mod)%mod;

Modified Code

#4

I had undesrtood this approach using modular arthimetic properties. My doubt is that, why can’t we calculate the final result and then do the modulo?

#6

What we did using the modulo addition expansion in stepwise calculation, Shouldn’t it be same as calculating the final result and then taking the modulo with 10^9+7 ??

#7

maximum Value that can be stored in int variable is 2147483647, whenever it will encounter it, you int variable will either give you tle or segmentation fault. To avoid this we always do modulo to ignore that limit.
you can read more about modulo from here https://www.geeksforgeeks.org/modulo-1097-1000000007/

#8

So ideally (mathematically),

  1. the thing that we are doing stepwise and storing
  2. Calculating the result and then taking modulo
    These two should have the same value? And we are choosing option 1 due to storage limits?
#9

see understand it, if you are calculating result without taking modulo stepwise. If In between your int variable limit reaches, then if you still add 1 in your upcoming result it will give you TLE or SEIGEV
but if you are taking stepiwse modulo from the calculated result, you will never touch this intt variable limit. and you can still add upcoming results in your variable. Understood?

#10

Yeah got it, thank you

#11

marking it as resolve

#12

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.