I found this coin change problem code in hackerrank.

Question

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

Answer 1

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.

Answer 2

Tq buddy I was just confused Abt that input part which made it look complex now it works fine.

Answer 3

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.

Answer 4

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 :)

Answer 5

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

Answer 6

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 )