LC 322 - Coin Change
Question
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:
1
2
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
1
2
Input: coins = [2], amount = 3
Output: -1
Example 3:
1
2
Input: coins = [1], amount = 0
Output: 0
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Links
Question here and solution here
Solution
concept
top down memoization
For the first two solution, we run DFS based on the index of the coins but for some reason the memoization do not work. The reason is because there are the same (i, cur_sum) can have multiple len(cur) from other branch which is the answer, but if we run other branch, the cache will not be updated but return the cached value (which might not be correct) immediately.
The NeetCode solution keep track of the remain amount need to be filled and at each step it exhaustively search through all the coins combination and only then cache the results for that particular remain amount and it works
bottom up solution
Here the subproblem is what is the least amount of coins needed to match the amount where it is from 0, 1, 2, … , amount, at each step we can reuse the solved problem (if it is already solved).
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class Solution:
"""
Brute force DFS
TLE
"""
def coinChange(self, coins: List[int], amount: int) -> int:
cur = []
result = []
def dfs(i):
if i >= len(coins) or sum(cur) > amount:
return
if sum(cur) == amount:
result.append(len(cur))
return
cur.append(coins[i])
dfs(i)
cur.pop()
dfs(i+1)
dfs(0)
return min(result) if result else -1
class Solution:
"""
Brute force solution
TLE
but this time the logic is every step we minimise by choose the min of 2 choices
"""
def coinChange(self, coins: List[int], amount: int) -> int:
cur = []
result = []
def dfs(i, cur_sum):
if cur_sum > amount or i >= len(coins):
return float('inf')
if cur_sum == amount:
return len(cur)
# choose current coin
cur.append(coins[i])
take = dfs(i, cur_sum + coins[i])
cur.pop()
# skip current coin
skip = dfs(i + 1, cur_sum)
return min(take, skip)
ans = dfs(0, 0)
return ans if ans != float('inf') else -1
class NeetSolution:
"""
Brute force solution
TLE
track remain amount to be matched.
"""
def coinChange(self, coins: List[int], amount: int) -> int:
def dfs(remain_amt):
if remain_amt == 0:
return 0 # amount of coins needed to achieve remain_amt
# each recursive call should start fresh, ans represents the minimum for that particular remain_amt, not shared among all recursive branches.
ans = float("inf")
for coin in coins:
if remain_amt - coin >= 0:
ans = min(ans, 1 + dfs(remain_amt - coin)) # each time use up one coin to go to next stage
return ans
min_coins = dfs(amount)
return -1 if min_coins == float("inf") else min_coins
class Solution:
"""
top down (memoization)
"""
def coinChange(self, coins: List[int], amount: int) -> int:
cache = {}
def dfs(remain_amt):
if remain_amt == 0:
return 0 # amount of coins needed to achieve remain_amt
if remain_amt in cache:
return cache[remain_amt]
# each recursive call should start fresh, ans represents the minimum for that particular remain_amt, not shared among all recursive branches.
ans = float("inf")
for coin in coins:
if remain_amt - coin >= 0:
ans = min(ans, 1 + dfs(remain_amt - coin))
cache[remain_amt] = ans
return cache[remain_amt]
min_coins = dfs(amount)
return -1 if min_coins == float("inf") else min_coins
class Solution:
"""
bottom up solution
"""
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float("inf")] * (amount + 1) # from 0 -> amount
dp[0] = 0 # need 0 coin to reach 0 amount
# sub problem is least amount of coins to reach amt = 0, 1, 2, ... amount
for amt in range(1, amount + 1):
for coin in coins:
if amt - coin >= 0:
dp[amt] = min(dp[amt], 1 + dp[amt - coin]) # reuse solved problem if it exist, else it is just inf
return dp[-1] if dp[-1] != float("inf") else -1
Complexity
time: $O(n*t)$ where $n$ is length of coins array and $t$ is amount
space: $O(t)$