Given an array of coins or denominations and a target sum, calculate the minimum number of coins required to match the total. Note that the coins array will have denominations that are Infinitely available, i.e. coins can be repeated and added to calculate the target.
We are going to use dynamic programming to build our
ways array as we traverse the coins / denominations array.
waysarray which will hold all the numbers climbing upto the target element. For example, if the
target = 6, then the
waysarray length of the array will be =
7and the indices will reach till 6. Initialize all the values inside of the array with
ways = 0since there are no ways to create a
waysarray is simple, every index donates the target element for that particular value. For example,
waysdenotes what is the minimum number of ways to make
$3with whatever we have now. This will eventually build up to
wayswhich is what we are looking for.
coinsarray to loop over current coin being traversed.
waysarray and check IF THE CURRENT COIN DENOMINATION IS LESS THAN OR EQUAL TO THE INDEX / AMOUNT VALUE. If that is true, We implement the following formula to calculate the minimum value:
ways[amount] = Math.min(ways[amount], 1 + ways[amount - coins[i]])
For example, If current coin being traversed is
1 and we are at
3 index for ways - the formula becomes:
ways = Math.min(ways, 1 + ways[3 - 1]
This builds up to
ways which is returned at the end.
nis the target and
dis the length of denominations array.
O(n)Space: Because we create a
waysarray of length