MONEY CHANGE help

#1

question = https://hack.codingblocks.com/contests/c/452/1026
solution = https://ide.codingblocks.com/#/s/23881

#2

Here is my code:
https://ide.codingblocks.com/#/s/24270

First i made corrections to your code and submitted it but it gave run-time error for quite a lot of cases. This is because you used Top-Down DP. In top-down dp, the recursion stack is sometimes full because of which we get runtime error. Because size of recursion stack is just 10^4 but iteration can handle around 10^7. So i submitted it using Bottom-Up DP and it got accepted.
Also, this problem can be solved by 1D Dp in same time complexity as well.

1 Like