Najmniej monet tablicą

Wydawanie reszty dynamicznie i porównanie z metodą zachłanną - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

`best[k]` to najmniejsza liczba monet dla kwoty `k`. Kwotę `k` kończy jakaś moneta `c`, a reszta `k - c` jest wydana najlepiej, więc `best[k] = 1 + min(best[k - c])`. Liczymy od `k = 1` w górę. To programowanie dynamiczne: każda kwota liczona raz, z wyników mniejszych.

coins = [1, 3, 4]
amount = 10
INF = float("inf")
best = [0] + [INF] * amount
for k in range(1, amount + 1):
    for c in coins:
        if c <= k and best[k - c] + 1 < best[k]:
            best[k] = best[k - c] + 1
print(best)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.