LeetCode-Coin Change Problem (Python)Tags: Algorithm, coin change dynamic programming, dynamic programming
You are given coins of different denominations and a total amount of money amount. Write a function to compute 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, 2, 5], amount =
3 (11 = 5 + 5 + 1)
, amount =
You may assume that you have an infinite number of each kind of coin.
To solve a minimization problem, we need to identify the subproblem, and use the subproblem to solve the original problem. Here I will talk about how to come up a solution based on dynamic programming with
O(mn) space complexity. Then we optimize the space complexity to
Lets number the coins from 1 to M. Suppose we know the answer wheun only use the coins from
1 to M - 1, how can we use that to solve the problem using coins from
1 to M?
Num(m, n) as the minimum number of coins to get amount n when the coins from
1 to m are used.
Now we want to solve
Num(m+1, n), which means the minimum number of coins to get amount n when coins from 1 to m+1 are used.
Actually, there are only two options: use the
(m + 1) th coin, or not use it.
There are two cases:
coin[m + 1] is larger than n, we can not use it. so Num(m + 1, n) = Num(m, n)
Num(m + 1, n) = Min( Num(m, n), Num(m + 1, n - coin[m + 1]) + 1), where coin[m + 1] denotes the value of coin m + 1
Be careful, as there are infinite coins,
Num(m + 1, n - coin[m + 1]) should be used here. If you use
Num(m, n - coin[m + 1]), it means each coins can only be used once.
Here is the implementation:
def coin_change(coins, N):
M = len(coins) # number of coins
Num = [[float('inf') for _ in range(N + 1)] for i in range(M + 1)]
for m in range(M + 1):
for n in range(N + 1):
# m = 0: no coins used
# n = 0: amount is 0
if m == 0 or n == 0:
if n == coins[m - 1]:
Num[m][n] = 1
if coins[m - 1] <= n:
Num[m][n] = min( Num[m][n], Num[m - 1][n], Num[m][n - coins[m - 1]] + 1)
Num[m][n] = Num[m - 1][n]
return -1 if Num[M][N] == float('inf') else Num[m][n]
As the space complexity is
O(M * N) is cann’t pass big N. We can reduce the space complexity to O(N) as for each run there is only two rows affected.
Num[n] as the minimum number of coins should be used, then we iterate through the m coins, and check whether Num[n] is larger than
Num[n - coins[m]] + 1 when n is larger than coins[m].
Here is the optimized implementation with O(n) space complexity.
def coin_change_optimized(coins, N):
Num = [float('inf') for _ in range(N + 1)]
#0 coins needed when the amount is 0
Num = 0
for n in range(N + 1):
for coin in coins:
if coin <= n:
Num[n] = min(Num[n], Num[n - coin] + 1)
return -1 if Num[N] == float('inf') else Num[n]