Coin change problem

#1

I think this solution is right i have implemented using top down approach but it showing wrong answer .It might be have silly mistake please check the solution

#2

@jaiskid Your dp logic is not correct as in recursion two parameters are changing that is sum and number of coins ,so it will not work with 1d dp array in which you have taken n only ,you have to take 2d dp array for sum and number of coins as well.Try this logic ,hope you get it.If you have any doubt feel free to ask.
Happy coding :slight_smile:

#3

@rishabhmahajan546 hey rishabh so you’re saying that there is no topdown solution exist for this problem.

#4

@jaiskid you can use topdown approach but instead of array you have to take map and keys of map should be combination of sum and no of coins you can concatenate both and give them form of key of map so that each case behaves uniquely.Hope you get it.
:slight_smile:

#5

@rishabhmahajan546 hey rishabh like key value pair kind of in which left side keys as coins and right side sum

#6

@jaiskid no like in dp array you have taken sum as index and its value as dp value so in map take combination of sum and no of coins as key and value will be dp value.
Eg. Map[no coins+sum]= dp value;

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.