Coin change problem

dynamic-programming

#1

How to solve coin change problem if we have limited number of coins?


#2

You can keep a map consisting of the count of each coin value. Each time you use a coin, decrement it’s count in the map. If while adding a coin if you see that the count of the coin value is <= 0, then don’t add the coin. I guess this might solve the problem.


#3

You can make a array of total coins given. For e.g., let’s assume there are 4 coins given {1,2,3,4} and each of 2 units then make a array of {1,1,2,2,3,3,4,4} and then proceed for normal approach of DP how many times you can make up to ‘N’.


#4

it would again make the complexity go back to O(2^n) how would we do dp on this problem assuming we have only one of a kind coin?