Coin Change
Statement
Given an integer total, and a list of integers coins that represent different coin denominations, find the minimum number of coins needed to make the total amount. It it’s impossible, then return -1. If the total amount is 0, then return 0.
Constraints
- 1 ≤
coins.length()≤ 12 - 1 ≤
coins[i]≤ 10⁴ - 0 ≤
total≤ 900
Solution
"""
production algorithm
"""
class Solution:
def coin_change(self, coins, total):
"""
time complexity O(tc)
space complexity O(t)
"""
memo = [0 if t == 0 else None for t in range(total + 1)]
for t in range(1, total + 1):
k = float("inf")
for c in coins:
if c <= t:
k = min(k, 1 + memo[t - c])
memo[t] = k
if memo[total] == float("inf"):
return -1
return memo[total]"""
unit tests
"""
from unittest import TestCase
from algorithms.dynamic_programming.coin_change.solution import Solution
class SolutionTestCase(TestCase):
def test_zero_solution(self):
# Given
coins = [2, 3, 4, 5, 6, 7, 8, 10]
total = 0
solution = Solution()
# When
actual = solution.coin_change(coins, total)
# Then
expected = 0
self.assertEqual(actual, expected)
def test_nonexistent_solution(self):
# Given
coins = [2, 3, 4, 5, 6, 7, 8, 10]
total = 1
solution = Solution()
# When
actual = solution.coin_change(coins, total)
# Then
expected = -1
self.assertEqual(actual, expected)
def test_existent_solution(self):
# Given
coins = [2, 3, 4, 5, 6, 7, 8, 10]
total = 32
solution = Solution()
# When
actual = solution.coin_change(coins, total)
# Then
expected = 4
self.assertEqual(actual, expected)Strategy
Dynamic Programming.
Explanation
A 1-D matrix, whose dimension is the total amount, is maintained to hold the optimal solution to the problem for the total seen so far. In the trivial case, where the total is 0, the optimal solution is 0. Then, iteration of the total and coins occurs. The optimal solution for a smaller total is used to find the optimal solution for a larger total. Iteration ends when the optimal solution has been found for the input total.
Notice, that the problem has optimal substructure, i.e. the optimal solution of a larger total amount can be found from the optimal solution of a smaller total amount. Also notice, that the problem has overlapping subproblems, i.e. the optimal solution of a smaller total amount can be reused to find the optimal solution of distinct larger total amounts. Since the problem has optimal substructure and overlapping subproblems, then dynamic programming can be used to solve the problem.
Time Complexity
Iteration of the total and coins has time complexity O(tc). Therefore, the time complexity of the algorithm is O(tc).
Space Complexity
The auxiliary space complexity depends on the size of the matrix which is t. Therefore, the auxiliary space complexity of the algorithm is O(t).
