Given a variety of coin types defining a currency system, find the minimum number of coins required to express a given amount of money. Assume infinite supply of coins of every type.
Input: Coin types: [1, 3, 5]. Amount to express: 9.
Output: 3
Here are all the unique ways to express 9 as a sum of coins 1, 3 and 5:
1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 3
1, 1, 1, 1, 5
1, 1, 1, 3, 3
1, 3, 5
3, 3, 3
Last two ways use the minimal number of coins, 3.
Every input will include a coin of value 1. This guarantees that a solution will always exist.
There will be no duplicate coin types in the input.
● 1
● 1
● 1
We've provided two solutions.
We will follow the following recursive definition:
If value == 0:
// Zero coins are required to express the value of 0.
// End of recursion. Base case.
return 0
If value > 0:
minimum_coins(value) = min {1 + minimum_coins(value-coins[i])} (where i belongs to [0,n-1] and coins[i]
Basically what we are doing here is exhaustively searching for all the possible combinations of denominations which can generate our desired value and maintain a minimum number of coins required to generate that value and that will be our answer.
This method is not efficient as it computes subproblems again and again.
O(n^value).
Auxiliary Space Used:
O(value). That’s the maximum number of the recursive calls at a time.
O(n + value).
Input takes O(n) and the auxiliary space used is O(value).
It is fairly intuitive that the brute force method computes subproblems again and again, so we need to cache the data.
It can be easily done using the bottom-up DP approach. We will use a one-dimensional array as a DP table which at the i-th index stores the minimum number of coins required to value the value i.
Base case: dp[0]=0, other values in the array are set to the positive infinity.
We use 2 loops:
The 1st loop(i) iterates over 1..value.
The 2nd loop(j) iterates over the given coin types.
For every value of i and coins[j] we check if that i (current value to be expressed) is greater than or equals to the coin value, i.e. i>=coins[j]. If yes, then we update dp[i] = min(dp[i],1+dp[i-coins[j]]).
After the dp table has been constructed, dp[value] will
give us our answer.
O(n*value).
The outer loop makes value iterations and the inner one makes n iterations.
Auxiliary Space Used:
O(value).
The size of the dp array.
O(n + value).
Input takes O(n) and the auxiliary space used is O(value).