Table of contents
Open Table of contents
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 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: 1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Constraints:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31  1
0 <= amount <= 10^4
Explanation/Approach
The “Coin Change” problem is a classic example of dynamic programming. The idea is to build a solution iteratively while solving smaller subproblems. We use an array dp
where dp[i]
will represent the minimum number of coins needed to make up the amount i
.
Dynamic Programming Approach:
 Initialization: We initialize an array
dp
of sizeamount + 1
with a large value (likeamount + 1
) since the minimum number of coins needed can never exceed the amount.  Base Case:
dp[0]
is set to 0 because no coins are needed to make up amount 0.  Iteration: For each coin value in
coins
, we update thedp
array. For every amounti
from the value of the coin up toamount
, we calculatedp[i]
as the minimum ofdp[i]
anddp[i  coin] + 1
. This represents the minimum number of coins needed to make the amounti
, considering the current coin.  Result: After filling the
dp
array, ifdp[amount]
is still greater thanamount
, it means it’s not possible to make up that amount with the given coins, so we return 1. Otherwise, we returndp[amount]
.
Solution: Dynamic Programming
class Solution:
def coinChange(self, coins: List[int], amount: int) > int:
# Initialize the dp array with amount + 1, which is an impossible high number of coins
dp = [amount + 1] * (amount + 1)
dp[0] = 0 # Base case: No coins needed for amount 0
# Iterate over each coin
for coin in coins:
# Update the dp array for each amount
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i  coin] + 1)
# If the amount is not achievable, return 1
return dp[amount] if dp[amount] != amount + 1 else 1
Time and Memory Complexity
The time complexity is O(n*m) where n is the amount
and m is the number of coins, as we iterate over each coin for each amount up to amount
. The space complexity is O(n) due to the additional array dp
used for dynamic programming.
Explanation
The dynamic programming solution builds up the minimum number of coins needed for each amount up to the target amount. It iterates through each coin, updating the dp
array to reflect the minimum coins needed for each amount. If the final amount can’t be achieved with the given coins, the function returns 1, indicating it’s not possible.
Visualization Process:

Initialize the DP Array:
 We start with a
dp
array wheredp[i]
represents the minimum number of coins needed to make the amounti
.  Initialize
dp
with a size ofamount + 1
(12 in this case) and set all values to a large number (12 here) except fordp[0]
, which is set to 0.  Initial
dp
array:[0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
 We start with a

Process Coin 1:
 For each amount from 1 to 11, we check if using a coin of 1 helps in reducing the number of coins.
 Updated
dp
:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Process Coin 2:
 Start from amount 2. Check if using a 2coin is better than the current number of coins in
dp
.  After processing coin 2:
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
 Start from amount 2. Check if using a 2coin is better than the current number of coins in

Process Coin 5:
 Start from amount 5. Check if using a 5coin is better than the current number of coins in
dp
.  Final
dp
:[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
 Start from amount 5. Check if using a 5coin is better than the current number of coins in
Final Output:
 The value at
dp[11]
is3
, indicating the minimum number of coins needed to make 11 is 3.  The coins used are two 5s and one 1.
Visual Representation:
Coin: 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Coin: 2
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
Coin: 5
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
Result: Minimum coins for amount 11 is 3 (5 + 5 + 1)
Each step in the array represents the dynamic updating of the minimum coins needed for each amount. This visual representation shows how the solution evolves with each coin denomination.