How to solve this coin change problem on gfg

#1

https://practice.geeksforgeeks.org/problems/coin-change/0
i try to solve this using 1d dp but the output is wrong https://ide.codingblocks.com/s/279476 what is the problem in this code

#2

@rohitkandpal683 here refer the webinar it contains the video on it by prateek bhaiya and code


dont forget to hit like and mark resolved if cleared :smiley:

#3

https://ide.codingblocks.com/s/279476 i got the correct answer but dont know why my my output is wrong can you please check the difference i comment the correct please check the code

#4

@rohitkandpal683 ok wait let me check

#5

@rohitkandpal683 corrected

#6

the correct output is 4 and 5 but your output is 2 and 2 in both cases

#7

@rohitkandpal683 2+2=4 and 5+5=10 so ans should be 2 and 2 only

#8

@rohitkandpal683 ohhh we have to calculate no of ways not min no of coins wait let me check again

#9

yes we have to count total number of ways so the ans of 1st test case is 4 {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}.

#10

@rohitkandpal683 ok then whats the problem the commented part was correct, you have to first iterate on array then inner loop should be of cents as you have to calculate the total ways,

#11

I have only one doubt that why can’t I iterate on cents first then inner loop on the array because it also means that for each cent we check for all coins

#12

@rohitkandpal683 for that dry run for a small example you will understand
3
1 2 3
4
dry run for it