Anonymous user
Count the coins: Difference between revisions
Faster and shorter Python version, as Java
(Added PicoLisp) |
(Faster and shorter Python version, as Java) |
||
Line 539:
def count_changes(amount_cents, coins):
n = len(coins)
cycle = max([c+1 for c in coins if c <= amount_cents]) * n
table = [0] * cycle
for i in xrange(n):
Line 545 ⟶ 546:
pos = n
for s in
for i in
if i == 0 and pos >= cycle:
pos = 0
if coins[i] <= s:
q = pos -
table[pos] = table[q] if (q >= 0) else table[q + cycle]
if i:
table[pos] += table[pos - 1]
pos += 1
return table[pos - 1]
| |||