solution link:https://www.codechef.com/viewsolution/14156262 problem link:https://www.codechef.com/problems/COINS what is wrong with the solution? asked 08 Jun '17, 16:46

You are doing a basic error. Lets say the coin value is X. We see that X/2 +X/3+X/4 is greater than X. Good! But we can further break that X/2 , X/3 and X/4 into even smaller pieces such that we get more coins. Eg lets take X=100 We get coin 50,33,25. Now we can divide 50 to 25, 16,12. Similarly we can do to 33 and 25. Meaning, you have to do the process on and on, until dividing into smaller coins yields no profit. (Maths will show that this for X<=12 , we get no profit) What you will ahve to do is recursion +memonisation. But how will you store the values? (As such large array isnt possible) In C++, there is a data structure called maps. Its speciality is that, you can define the "key" by which you will access the element. So when you say map[x]=x, it will store x and make a key "x" to access it. (Do some research on it if needed) OR You can just store results for values <=10^7 or 10^8 in array and still happily solve the question. Get back to me if doubt exists. answered 08 Jun '17, 17:45

This is a basic dp question and here is my accepted solution https://www.codechef.com/viewsolution/12741814 if you still have any doubt then feel free to comment answered 08 Jun '17, 16:52
