Problem
You are given an integer array coins
representing coins of different denominations and an integer amount
representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1
.
You may assume that you have an infinite number of each kind of coin.
Example
Example 1:
|
|
Example 2:
|
|
Note
There is another simpler version or variant of the problem Coin Change with Fewest Number of Coins Given Canonical System and Infinite Supply. We will solve generic case here, but the canonical system is easier to solve with greedy approach.
Solution
For every coin, we have two choices: either to include it or exclude it. Thus, we can evaluate both scenarios and select the optimal solution, which in this context is the minimum among all possible solutions.
To solve this, we first decompose the problem into smaller subproblems. But what exactly are these subproblems?
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Recursion
Let’s say we have a set of 3 coins: {1, 2, 5}
, representing denominations of one unit, two units, and five units respectively. To find the solution, we need to determine which of the following is the minimum: using a coin of denomination 1
plus the number of coins required for the remaining amount after subtracting 1
, using a coin of denomination 2
plus the number of coins required for the remaining amount after subtracting 2
, or using a coin of denomination 5
plus the number of coins required for the remaining amount after subtracting 5
.
The number of coins needed for the original amount is thus calculated as follows:
$$ numCoins = \begin{cases} 1 + numCoins(originalAmount - 1) \\ 1 + numCoins(originalAmount - 2) \\ 1 + numCoins(originalAmount - 5) \\ \end{cases} $$
However, this algorithm is highly inefficient. For instance, if we need to make change for 7 cents (A = 7), the recursion tree would appear as follows:
graph TD A(7) -->|1| B(6) A -->|2| C(5):::yellow A -->|5| D(2) B -->|1| E(5):::yellow B -->|2| F(4) B -->|5| G(1) C -->|1| H(4) C -->|2| I(3) C -->|5| J(0):::green D -->|1| K(1) D -->|2| L(0):::green D -->|5| M("-3"):::red E --> Incomplete1["..."] F -->|1| N(3) F -->|2| O(2) F -->|5| P("-1"):::red H -->|1| Q(2) H -->|2| R(1) H -->|5| S("-2"):::red G -->|1| T(0):::green G -->|2| U("-1"):::red G -->|5| V("-4"):::red K -->|1| W(0):::green K -->|2| X("-1"):::red K -->|5| Y("-4"):::red N --> Incomplete5["..."] O --> Incomplete6["..."] Q --> Incomplete7["..."] R --> Incomplete8["..."] classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff; style Incomplete1 display:none style Incomplete5 display:none style Incomplete6 display:none style Incomplete7 display:none style Incomplete8 display:none classDef yellow fill:#FFD700,stroke:#000,stroke-width:1px,color:#000;
In the image we can see that tree is expanding at least 2 times from 5
itself, so that is really inefficient. But we also have repeating subproblems for 4
, 3
, 2
, 1
etc.
The time complexity of above solution is exponential. Every coin has 2 options, to be selected or not selected.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n^A)
wheren
is number of coins andA
is the amount. The recursion tree depth is equal to theA
(the target amount). This is because we reduce the amount step by step until it reaches0
or becomes negative. At each level of recursion, we haven
branches (one for each coin denomination). - 🧺 Space complexity:
O(A)
. The maximum recursion depth is equal toA
(in the worst-case scenario where the coin denomination is1
, requiringA
recursive calls to reduce the amount to0
).
Method 2 - Top Down DP
To improve the efficiency, we use memoization to store the results of subproblems that have already been computed. This helps avoid re-computation and reduces the time complexity.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(A*n)
- Each amount from
0
toA
(whereA
is the target amount) is solved only once. - For each amount, we iterate through
n
coins. - Thus, the time complexity is
O(A * n)
.
- Each amount from
- 🧺 Space complexity:
O(A)
- Space for the memoisation table is
O(A)
(since amounts are stored from0
toA
). - Recursive call stack depth is at most
O(A)
(in the worst case).
- Space for the memoisation table is
Method 3 - Bottom up DP
Let’s see how we can apply dynamic programming (DP) to solve this problem effectively.
1. Optimal Substructure
Given coin denominations coins[]
and the target amount A
, we recognize that we can build the solution using the substructure property. Here’s a revised view:
|
|
2. Overlapping Subproblems
With a naive recursive implementation, we would repeatedly calculate the same subproblems which is inefficient. Here’s how we can use dynamic programming:
|
|
dp[i]
represents the minimum number of coins needed to make the amounti
.- For each coin, if we include the coin in the solution, we add
1
to the result ofdp[i - coin]
.
Detailed Steps
- We maintain an array
dp[]
wheredp[i]
represents the minimum number of coins needed for the amounti
. - Initialize
dp[]
with a high value (e.g.,Integer.MAX_VALUE
) and setdp[0]
to0
since no coins are required to make an amount of0
. - Using a bottom-up approach, we fill out the array
dp[]
for all values from0
toamount
. - The final solution will be in
dp[amount]
which will give us the minimum number of coins required to make the amountn
. If it remains asInteger.MAX_VALUE
, it means the target amount cannot be made with the given denominations.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(A*n)
- We iterate through all amounts from
1
toA
(the target amount), and for each amount, we iterate through alln
coin denominations. - Thus, the total number of steps is proportional to
A * n
.
- We iterate through all amounts from
- 🧺 Space complexity:
O(A)
, as we use a singledp
array of sizeA + 1
to store the minimum coins required for each amount.
Dry Run
Let’s dry run the code for amount = 13
and coins = [7, 2, 3, 6]
using the bottom-up dynamic programming approach.
Initial Setup
- Array
dp[]
Initialization:dp[0] = 0
(0 coins to make amount 0).- All other
dp[i]
initialized toamount + 1
(infinity in this context).
Initial dp
Array
|
|
Filling dp[]
Array
We iterate over each amount from 1
to 13
and for each coin.
Iteration for i = 1
- Coin = 7:
i - coin < 0
, no update. - Coin = 2:
i - coin < 0
, no update. - Coin = 3:
i - coin < 0
, no update. - Coin = 6:
i - coin < 0
, no update.
|
|
Iteration for i = 2
- Coin = 7:
i - coin < 0
, no update. - Coin = 2:
dp[2] = min(dp[2], dp[2 - 2] + 1) => dp[2] = min(inf, 0 + 1) => 1
.1
dp = [0, inf, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
- Coin = 3:
i - coin < 0
, no update. - Coin = 6:
i - coin < 0
, no update.
Iteration for i = 3
-
Coin = 7:
i - coin < 0
, no update. -
Coin = 2: No update as
dp[3 - 2] + 1
continues to result ininf
. -
Coin = 3:
dp[3] = min(dp[3], dp[3 - 3] + 1) => dp[3] = min(inf, 0 + 1) => 1
.1
dp = [0, inf, 1, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
-
Coin = 6:
i - coin < 0
, no update.
Iteration for i = 4
- Coin = 7:
i - coin < 0
, no update. - Coin = 2:
dp[4] = min(dp[4], dp[4 - 2] + 1) => dp[4] = min(inf, 1 + 1) => 2
.1
dp = [0, inf, 1, 1, 2, inf, inf, inf, inf, inf, inf, inf, inf, inf]
- Coin = 3:
dp[4]
continues to be2
after attempting to update withdp[1] + 1
. - Coin = 6:
i - coin < 0
, no update.
Iteration for i = 5
- Coin = 7:
i - coin < 0
, no update. - Coin = 2: No update as
dp[5 - 2] + 1
continues to result in2
. - Coin = 3:
dp[5] = min(dp[5], dp[5 - 3] + 1) => dp[5] = min(inf, 1 + 1) => 2
.1
dp = [0, inf, 1, 1, 2, 2, inf, inf, inf, inf, inf, inf, inf, inf]
- Coin = 6:
i - coin < 0
, no update.
Iteration for i = 6
- Coin = 7:
i - coin < 0
, no update. - Coin = 2: No update as
dp[6 - 2] + 1
continues to be3
. - Coin = 3: No update as
dp[6 - 3] + 1
continues to be2
. - Coin = 6:
dp[6] = min(dp[6], dp[6 - 6] + 1) => dp[6] = min(inf, 0 + 1) => 1
.1
dp = [0, inf, 1, 1, 2, 2, 1, inf, inf, inf, inf, inf, inf, inf]
Iteration for i = 7
- Coin = 7:
dp[7] = min(dp[7], dp[7 - 7] + 1) => dp[7] = min(inf, 0 + 1) => 1
.1
dp = [0, inf, 1, 1, 2, 2, 1, 1, inf, inf, inf, inf, inf, inf]
- Coin = 2: No update as
dp[7 - 2] + 1
continues to be3
. - Coin = 3: No update as
dp[7 - 3] + 1
continues to be2
. - Coin = 6: No update.
Iteration for i = 8
-
Coin = 7: No update.
-
Coin = 2:
dp[8] = min(dp[8], dp[8 - 2] + 1) => dp[8] = min(inf, 1 + 1) => 2
.1
dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, inf, inf, inf, inf, inf]
-
Coin = 3: No update as
dp[8 - 3] + 1
continues to be3
. -
Coin = 6:
dp[8] = min(dp[8], dp[8 - 6] + 1) => dp[8] = min(2, 1 + 1) => 2
.
Iteration for i = 9
-
Coin = 7: Update becomes higher, so no change.
-
Coin = 2: No change as
dp[9 - 2] + 1
is 2 as well. -
Coin = 3:
dp[9] = min(dp[9], dp[9 - 3] + 1) => dp[9] = min(dp[9], 2) => 2
. -
Coin = 6:
dp[9] = min(dp[9], dp[9 - 6] + 1) => dp[9] = min(dp[9], 3) => 3
.1
dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, inf, inf, inf, inf]
Iteration for i = 10
-
Coin = 7: Update becomes higher, so no change.
-
Coin = 2: No change as
dp[10 - 2] + 1
is 3. -
Coin = 3: No change as
dp[10 - 3] + 1
updates it to 1. -
Coin = 6: No change as
dp[10 - 6] + 1
results the same.1
dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 2, inf, inf, inf]
Iteration for i = 11
-
Coin = 7: No change as adding increment results higher.
-
Coin = 2:
dp[11 - 2] + 1
results the optimal list count. -
Coin = 3: No change as adding increment results higher.
-
Coin = 6: No change as adding increment results 3.
1
dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, inf, inf]
Iteration for i = 12
-
Coin = 7: Update becomes higher, so no change.
-
Coin = 2: Update gets optimal value.
-
Coin = 3: No change as recursion results extra
+1
. -
Coin = 6:`dp[12 -6] results the minimum.
1
dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, 2, inf]
Iteration for i = 13
- Coin = 7:-update not needed as recursion count adds the extra.
- Coin = 2: update returns optimal value as needed.
- Coin 3: No changes required as list includes the count
- Coin 6: Update is optional as no list recurrence added.
Final Result`
Finally, our output count returns:
|
|
Method 4 - Using Bottom-up DP + Sorting
We can improve the speed a bit, if we sort the coins denominations:
Code
|
|
Complexity
- ⏰ Time complexity:
O(A*n)
- 🧺 Space complexity:
O(A)
Method 5 - Using Breadth First Search
Most dynamic programming problems can also be solved using BFS.
This problem can be visualised as reaching a target position with steps taken from the array of coins. We use two queues: one to track the current amount and the other for the minimal steps taken.
Dry run with:
|
|
Code
|
|
Complexity
- ⏰ Time complexity:
O(n * A)
- 🧺 Space complexity:
O(A)
for storing amounts and corresponding steps in queue