+ 3

I found this coin change problem code in hackerrank.

This code determines the no of ways of making change from the given types of coins but I can't be able to crack the working of this code can somebody explain it to me.I am attaching the complete question below https://www.hackerrank.com/challenges/coin-change/problem https://code.sololearn.com/czOgblLX2n60/?ref=app

11th Jul 2019, 12:11 PM
viki
viki - avatar
6 odpowiedzi
+ 2
Hi, This technique is called Dynamic Programming. Dynamic Programming is a bit like recursion in the way that you split the problem into smaller problems and you use them to solve the original one. In this case what the original author did is that he calculated how many ways you can change a value of 'j'. This is stored in dp[j]. This method is can be a bit confusing at first, but it's very powerful and worth your time to understand it.
13th Jul 2019, 9:58 AM
László Ozsvárt
László Ozsvárt - avatar
+ 1
Tq buddy I was just confused Abt that input part which made it look complex now it works fine.
13th Jul 2019, 10:44 AM
viki
viki - avatar
0
Ya it feels confusing.I know this is dynamic programming but the problem is I can't find the flow of the program and the way of giving the input.I tried to put this code in hackerrank ide but it gives wrong output and this program has received a full 60 score.
13th Jul 2019, 10:15 AM
viki
viki - avatar
0
Can you give an example where it gives a wrong output? But on the input i can't help much, i haven't written a line in C/C++ for years :)
13th Jul 2019, 10:17 AM
László Ozsvárt
László Ozsvárt - avatar
0
I tried to give the given input in hacker rank to the problem in a similar way but it was giving different output For example : For the input 4 3 1 2 3 Instead of printing 4 it's printing 3 And similarly for the input 10 4 2 5 3 6 Instead of giving 5 as output it's printing as 3 If I had tried other method it's giving me an error message of no response stdout
13th Jul 2019, 10:23 AM
viki
viki - avatar
0
The algorithm itself seems to be okay. I've cut out the input part and hardcoded the second input you wrote: https://code.sololearn.com/cVqCIPrU0hG1/?ref=app (Well, now i can't say that i haven't written c++ in years :D )
13th Jul 2019, 10:31 AM
László Ozsvárt
László Ozsvárt - avatar