-
Notifications
You must be signed in to change notification settings - Fork 42
/
coin-change.py
344 lines (301 loc) · 10.6 KB
/
coin-change.py
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
"""
322. Coin Change
Medium
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
"""
# V0
# IDEA : BFS
from collections import defaultdict
class Solution(object):
def coinChange(self, coins, amount):
"""
NOTE !!!
1) we use defaultdict(int)
2) we init steps via : steps[0] = 0
"""
steps = defaultdict(int)
steps[0] = 0
queue = [0]
while queue:
tmp = queue.pop(0)
level = steps[tmp]
if tmp == amount:
return level
for c in coins:
if tmp + c > amount:
continue
if tmp + c not in steps:
# queue += (tmp + c), # this is syntax suger, should be equal as below
queue.append(tmp + c)
steps[tmp + c] = level + 1
return -1
# V0'
# IDEA : DFS (TLE, need fix)
class Solution(object):
def coinChange(self, coins, amount):
# help func
def dfs(pt, rem, count):
if not rem:
self.res = min(self.res, count)
for i in range(pt, lenc):
if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
dfs(i, rem-coins[i], count+1)
coins.sort(reverse = True)
lenc, self.res = len(coins), 2**31-1
for i in range(lenc):
dfs(i, amount, 0)
return self.res if self.res < 2**31-1 else -1
# V0''
# IDEA : DFS, backtrack (TLE, need fix)
class Solution(object):
def coinChange(self, coins, amount):
# help func
def dfs(tmp):
#print (">>> tmp = {}, sum = {}".format(tmp, sum(tmp)))
if sum(tmp[:]) == amount:
#res.append(list(tmp[:]))
res.add(len(tmp[:]))
tmp = []
return res
if sum(tmp[:]) > amount:
cnt = 0
tmp = []
return
for i in coins:
if sum(tmp[:]) + i <= amount:
tmp.append(i)
dfs(tmp)
tmp.pop(-1)
# edge case
if amount == 0:
return 0
res = set()
tmp = []
coins = list(set(coins))
coins.sort()
dfs(tmp)
#print ("res = " + str(res))
return min(res) if res else -1
# V1
# http://bookshadow.com/weblog/2015/12/27/leetcode-coin-change/
# IDEA : DP
# DP state equation : dp[x + c] = min(dp[x] + 1, dp[x + c])
import collections
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [0] + [-1] * amount
for x in range(amount):
if dp[x] < 0:
continue
for c in coins:
if x + c > amount:
continue
if dp[x + c] < 0 or dp[x + c] > dp[x] + 1:
dp[x + c] = dp[x] + 1
return dp[amount]
### Test case : dev
# V1'
# http://bookshadow.com/weblog/2015/12/27/leetcode-coin-change/
# IDEA : BFS
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
steps = collections.defaultdict(int)
queue = collections.deque([0])
steps[0] = 0
while queue:
front = queue.popleft()
level = steps[front]
if front == amount:
return level
for c in coins:
if front + c > amount:
continue
if front + c not in steps:
queue += front + c,
steps[front + c] = level + 1
return -1
# V1''
# https://leetcode.com/problems/coin-change/solution/
# IDEA : DP (Top down)
# JAVA
# public class Solution {
#
# public int coinChange(int[] coins, int amount) {
# if (amount < 1) return 0;
# return coinChange(coins, amount, new int[amount]);
# }
#
# private int coinChange(int[] coins, int rem, int[] count) {
# if (rem < 0) return -1;
# if (rem == 0) return 0;
# if (count[rem - 1] != 0) return count[rem - 1];
# int min = Integer.MAX_VALUE;
# for (int coin : coins) {
# int res = coinChange(coins, rem - coin, count);
# if (res >= 0 && res < min)
# min = 1 + res;
# }
# count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
# return count[rem - 1];
# }
# }
# V1''
# https://leetcode.com/problems/coin-change/solution/
# IDEA : DP (BOTTOM UP)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# V1'''
# https://leetcode.com/problems/coin-change/discuss/114993/Four-kinds-of-solutions%3A-DP-BFS-DFS-improved-DFS
# IDEA : DP
class Solution:
def coinChange(self, coins, amount):
M = float('inf')
# dynamic programming
dp = [0] + [M] * amount
for i in range(1, amount+1):
dp[i] = 1 + min([dp[i-c] for c in coins if i >= c] or [M])
return dp[-1] if dp[-1] < M else -1
# V1''''
# https://leetcode.com/problems/coin-change/discuss/114993/Four-kinds-of-solutions%3A-DP-BFS-DFS-improved-DFS
# IDEA : BFS
class Solution:
def coinChange(self, coins, amount):
# BFS, graph search. Keep records of visited nodes
visited = [True] + [False] * amount
par = [0] # parents
child = [] # children
step = 0
while par:
step += 1
for p in par:
for c in coins:
tmp = p + c
if tmp == amount:
return step
elif tmp < amount and not visited[tmp]:
visited[tmp] = True
child.append(tmp)
par, child = child, []
return -1 if amount else 0
# V1'''''
# https://leetcode.com/problems/coin-change/discuss/114993/Four-kinds-of-solutions%3A-DP-BFS-DFS-improved-DFS
# IDDA : DFS
class Solution:
def coinChange(self, coins, amount):
if amount == 0:
return 0
coins.sort(reverse=True)
if amount < coins[-1]:
return -1
l = len(coins)
self.cur = float('inf')
# current answer(the worst case)
def dfs(ptr, rem, count):
'''ptr is the pointer to current index in coins,
rem denotes remainder. The money left to be made up.
count denotes current number of coins used.'''
if not rem: # remainder is 0, so one branch of dfs is done.
self.cur = min(self.cur, count)
else:
for i in range(ptr, l):
# this following if condition is marvelous!
if coins[i] <= rem < coins[i] * (self.cur - count):
# coins[i] <= rem gaurantees that 'rem' passed to following dfs will be positive
# if coins[i] * (self.cur - count) <= rem,
# then we know we cannot get better results
# just suppose coins[i] = 1, self.cur = 3, rem = 5.
# We can see there is no need to do dfs(i, 4, count+1).
dfs(i, rem-coins[i], count+1)
for i in range(l):
dfs(i, amount, 0)
return self.cur if self.cur < float('inf') else -1
# V1''''''
# https://leetcode.com/problems/coin-change/discuss/114993/Four-kinds-of-solutions%3A-DP-BFS-DFS-improved-DFS
# IDEA : DFS
class Solution:
def coinChange(self, coins, amount):
# improved dfs, use division first
l = len(coins) - 1
coins.sort(reverse=True)
self.ans = float('inf')
def dfs(start, rem, step):
if start > l:
return
div, mod = rem // coins[start], rem % coins[start]
if not mod:
self.ans = min(self.ans, step + div)
else:
rem, step = mod, step + div
dfs(start+1, rem, step)
if start < l:
for i in range(div):
rem += coins[start]
step -= 1
if (self.ans - step) * coins[start+1] > rem: # hope still exists
dfs(start+1, rem, step)
dfs(0, amount, 0)
return self.ans if self.ans < float('inf') else -1
# V1'''''''
# https://leetcode.com/problems/coin-change/discuss/77416/Python-11-line-280ms-DFS-with-early-termination-99-up
# IDEA : DFS
class Solution(object):
def coinChange(self, coins, amount):
# help func
def dfs(pt, rem, count):
if not rem:
self.res = min(self.res, count)
for i in range(pt, lenc):
if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
dfs(i, rem-coins[i], count+1)
coins.sort(reverse = True)
lenc, self.res = len(coins), 2**31-1
for i in range(lenc):
dfs(i, amount, 0)
return self.res if self.res < 2**31-1 else -1
# V2
# Time: O(n * k), n is the number of coins, k is the amount of money
# Space: O(k)
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
INF = 0x7fffffff # Using float("inf") would be slower.
amounts = [INF] * (amount + 1)
amounts[0] = 0
for i in range(amount + 1):
if amounts[i] != INF:
for coin in coins:
if i + coin <= amount:
amounts[i + coin] = min(amounts[i + coin], amounts[i] + 1)
return amounts[amount] if amounts[amount] != INF else -1