question link:https://hack.codingblocks.com/contests/c/547/1045
Since DP hasn’t done yet by Prateek bhaiya and this question is of recursion in online Course, I tried to do it using only recursion without DP but got time limit exceeded. Can I do it only using recursion?
Code link without DP: https://ideone.com/78vdAO
Hey Nipun, this problem can be done with recursion only without using DP but that will result into TLE due to many unnecessary recursive function calls. So, when you observe the sequence for this problem you will find that it is simple fibonacci sequence. Therefore, its better to solve this problem using a loop (i.e the iterative approach) having the time complexity of O(N) rather than using recursive approach have the time complexity O(2^N).
In the code I have used down-to-top approach. How can I use top-to-down?
Hey Nipun, I have also implemented this problem’s bottom-up approach only as its easy to think. If you want to refer the code for bottom-up approach you can refer my code.