when i am runnning my code it is showing correct output but when submitting the code is showing nothing. What am i doing wrong?
Tilling Problem - II
Hi @mikkyimran
When you are submitting the code you are getting most of the test cases as time limit exceeded because every recursive call is making 2 more calls that is why it is causing TLE. You should use bottom up dp approach to get an optimal solution.
Approach: For a given value of n and m, the number of ways to tile the floor can be obtained from the following relation.
count(n) = 1, 1 < = n < m
count(n) = 2, n = m
count(n) = count(n-1) + count(n-m), m < n
Hi @mikkyimran ,
there are some bugs in your code, first of all since the questions asks you to print answer modulo M(=1e9+7)
you should be careful at every sum you do like you are doing the sum of tiling(n-1,m)+tiling(n-m,m-1) , but here it might be possible that this sum might not fit in integer range, and it will overflow. Second thing is , your recurrence is wrong because , every time you will have two options either to place the tile horizontally (which is f(m-1) ways of tilling) OR you place m vertical tiles then you will have f(n-m) ways of tilling . So, in total there will f(n)=f(n-1)+f(n-m) ways of tilling.
Third thing is, since there are multiple test cases ,you can do either some typeof matrix exponentiation thing or you can do online using dp also. Your code with modified recurrence will still not work since its a recursion and it will take extra time for recursive stacks. If you implement the same thing in iterative approach , You won;t get any TLE.
Your code : https://ide.codingblocks.com/s/169430 (This code will still give tle because of recursive calls)
You can refer the code here for reference : https://ide.codingblocks.com/s/169429
If you still have doubts, please do ask.
Thanks,
Sir ! i haven’t studied DP . How can i pass the test cases using recursion?