problem : https://www.codechef.com/problems/COINS
my solution : https://www.codechef.com/viewsolution/24477751
I have checked solutions and i find they should take more time than my solution.
You are using only recursion. Use DP to store the answer for each n if it is not stored at present. This will result a better time complexity as you can reuse the previously calculated results.
2 Likes
@marksman, could you please explain reason of using DP please. I am not a novice but am a beginner. My username is sky_365. Furthermore, I am trying to solve COINS problem without using any arrays such as DP. However, online judge is showing that ‘TIME LIMIT EXCEEDED’.
Use memoization to save values which are already calculated.
Refer this: Memoization (1D, 2D and 3D) - GeeksforGeeks
1 Like