Coin Change

Q: Czy podejście odgórne czy oddolne jest lepsze w problemie wydawania reszty?

Oba wykonują tyle samo pracy: O(amount × coins) . Rekurencja odgórna może zagnieżdżać się na głębokość równą kwocie, co powoduje przepełnienie stosu wywołań przy 10^4 w kilku językach. Podejście oddolne wypełnia tabelę za pomocą pętli, więc nie ma ograniczenia głębokości i jest bezpieczniejszym wyborem na rozmowie kwalifikacyjnej.

ŚrednieProgramowanie dynamiczne

+10

Otrzymujesz listę coins z różnymi nominałami monet oraz docelową wartość amount. Możesz używać każdego nominału dowolną liczbę razy. Zwróć najmniejszą liczbę monet, których nominały sumują się dokładnie do amount, lub -1, jeśli żadna kombinacja monet nie pozwala uzyskać tej wartości. Wartość 0 wymaga 0 monet.

Funkcja

coinChange(coins: integer-array, amount: integer) → integer

coinsinteger-array: różne wartości monet, z których każdej można użyć dowolną liczbę razy
amountinteger: dokładną kwotę do zapłaty
Zwracainteger: najmniejsza potrzebna liczba monet lub -1, gdy nie da się uzyskać tej kwoty

Ograniczenia

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 10⁴
0 ≤ amount ≤ 10⁴
Wszystkie wartości monet są różne.

Przykłady

Wejście: coins = [2, 5, 10]amount = 27
Wyjście: 4
Wyjaśnienie: 10 + 10 + 5 + 2 daje 27 przy użyciu czterech monet. Trzy monety nie wystarczą: 27 jest nieparzyste, więc potrzebna jest dokładnie jedna 5, a pozostałe dwie dają co najwyżej 20, czyli za mało, by uzyskać 22.

Pytanie dodatkowe

Czy potrafisz policzyć, ile różnych kombinacji monet składa się na kwotę amount, zamiast szukać najmniejszej liczby monet?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Wybieranie największej pasującej monety nie działa: przy monetach 1, 3 i 4 kwotę 6 można zapłacić jako 4 + 1 + 1, podczas gdy 3 + 3 wymaga dwóch monet. Minimalna liczba monet dla danej kwoty zależy wyłącznie od minimalnej liczby monet dla mniejszych kwot, dlatego rozwiązujesz problem dla każdej kwoty od 0 do amount jeden raz.

Wypróbuj każdą kombinację, używając rekurencji

Poprawne, ale nie kończy się na największych testach

Intuicja

Jeśli ostatnia moneta, którą płacisz, ma wartość c, monety użyte wcześniej pozwalają zapłacić remaining - c możliwie najmniejszym kosztem. Zatem fewest(remaining) jest o jeden większe od najmniejszej wartości fewest(remaining - c) spośród wszystkich pasujących monet. Ta metoda sprawdza każdą sekwencję monet, która nie przekracza kwoty, więc nie może pominąć najlepszej.

Wciąż rozwiązuje te same kwoty. Przy monetach 2, 5 i 10 kwota 27 sprowadza się do 15 po zapłaceniu 10 + 2, 2 + 10, 5 + 5 + 2 i wielu innych kombinacjach, a za każdym razem oblicza 15 od początku. Liczba wywołań rośnie wykładniczo wraz z kwotą.

Algorytm

Napisz funkcję pomocniczą fewest(remaining), która zwraca najmniejszą liczbę monet dla remaining albo -1, jeśli żadna kombinacja nie zadziała.
Jeśli remaining wynosi 0, zwróć 0.
Dla każdej monety, której wartość nie przekracza remaining, wywołaj funkcję pomocniczą dla kwoty pozostałej po zapłaceniu tą monetą.
Zachowaj najmniejszy wynik różny od -1, powiększony o jeden za zapłaconą monetę.
Zwróć tę liczbę albo -1, jeśli każda moneta prowadziła donikąd. Odpowiedzią jest fewest(amount).

def coinChange(coins, amount):
    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        return best

    return fewest(amount)

Rekurencja z memoizacją

Poprawne, ale nie kończy się na największych testach

Intuicja

Rekurencja pyta tylko o kwoty od 0 do amount. Zapisz każdą odpowiedź w tablicy, gdy obliczasz ją po raz pierwszy, i zwracaj zapisaną wartość, gdy ta kwota pojawi się ponownie. Każda kwota jest rozwiązywana raz, w pętli przechodzącej po monetach: O(amount × coins) pracy.

Wywołania nadal zagnieżdżają się o jeden poziom na każdą wydaną monetę. Przy monecie o wartości 1 oznacza to nawet 10^4 poziomów, czyli więcej, niż pozwala domyślny stos wywołań w wielu językach.

Algorytm

Utwórz tablicę memo z miejscem na każdą kwotę od 0 do amount, przechowującą znacznik oznaczający, że nie została jeszcze obliczona.
W fewest(remaining) zwróć 0 dla 0, a jeśli memo[remaining] zawiera już odpowiedź, zwróć tę wartość.
W przeciwnym razie wypróbuj każdą pasującą monetę, tak jak w zwykłej rekurencji, i zachowaj najmniejszy wynik powiększony o jeden.
Zapisz wynik, również -1, w memo[remaining], zanim go zwrócisz.
Zwróć fewest(amount).

def coinChange(coins, amount):
    # memo[r] holds the answer for r once it is worked out; None means not yet
    memo = [None] * (amount + 1)

    def fewest(remaining):
        # The fewest coins that add up to remaining, or -1 if no mix does
        if remaining == 0:
            return 0
        if memo[remaining] is not None:
            return memo[remaining]
        best = -1
        for coin in coins:
            if coin <= remaining:
                rest = fewest(remaining - coin)
                if rest != -1 and (best == -1 or rest + 1 < best):
                    best = rest + 1
        memo[remaining] = best
        return best

    return fewest(amount)

Programowanie dynamiczne od dołu dla kwot

Intuicja

Wypełnij tablicę fewest od 0 wzwyż. Gdy dojdziesz do sumy t, każda mniejsza suma jest już rozpatrzona, więc fewest[t] jest o jeden większe od najmniejszej wartości fewest[t-c] spośród monet c, które się mieszczą.

Suma, której nie da się uzyskać żadnym zestawem monet, przechowuje znacznik amount + 1. Każda moneta jest warta co najmniej 1, więc poprawna odpowiedź nigdy nie używa więcej niż amount monet, a znacznik przegrywa każde porównanie. Pętla zastępuje rekurencję, więc głębokość stosu wywołań nigdy nie ma znaczenia.

Algorytm

Utwórz fewest z amount + 1 wpisami, wszystkie ustaw na wartość znacznika amount + 1, a fewest[0] ustaw na 0.
Dla każdej sumy t od 1 do amount sprawdź każdą monetę c, dla której c ≤ t.
Jeśli fewest[t-c] + 1 jest mniejsze niż fewest[t], zapisz tę wartość w fewest[t].
Po pętli zwróć -1, jeśli fewest[amount] nadal zawiera wartość znacznika, a w przeciwnym razie fewest[amount].

def coinChange(coins, amount):
    impossible = amount + 1
    fewest = [0] + [impossible] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and fewest[total - coin] + 1 < fewest[total]:
                fewest[total] = fewest[total - coin] + 1
    return fewest[amount] if fewest[amount] != impossible else -1

Pułapki i przypadki brzegowe

Najpierw wybieranie monety o największym nominale. Przy monetach 3 i 5 oraz kwocie 9 wydaje monety 5 i 3, zatrzymuje się przy kwocie 1 i zwraca -1, podczas gdy 3 + 3 + 3 działa.
Używanie największej liczby całkowitej jako znacznika. Dodanie do niej 1 powoduje przepełnienie do liczby ujemnej, która wygrywa potem każde porównanie. Użyj amount + 1.
Dodawanie 1 w ślepym zaułku. Gałąź zwracająca -1, powiększona o zapłaconą monetę, daje 0 i wygrywa każde porównanie. Pomijaj wyniki -1.
Rekurencja na głębokość amount poziomów. Przy monecie o nominale 1 i kwocie 10^4 Python zatrzymuje się po osiągnięciu domyślnego limitu 1000 poziomów, a JavaScript, Dart, Ruby i R również wyczerpują stos.
Odczytywanie fewest[t-c] dla monety o nominale większym niż t, przed początkiem tablicy.

Najczęstsze pytania3

Dlaczego podejście zachłanne nie sprawdza się w problemie wydawania reszty?

Wybieranie największej monety, która pasuje, jest bezpieczne tylko w przypadku niektórych systemów monetarnych, takich jak większość prawdziwych walut. Za pomocą monet o nominałach 1, 3 i 4 zapłacisz 6 trzema monetami zamiast dwiema, a monetami o nominałach 3 i 5 w ogóle nie da się zapłacić 9. Programowanie dynamiczne porównuje wszystkie możliwości, więc żaden system monetarny go nie zmyli.

Jaka jest złożoność czasowa problemu wydawania reszty?

Rozwiązanie z wykorzystaniem programowania dynamicznego działa w czasie O(amount × coins) i wymaga O(amount) miejsca: po jednym wpisie w tablicy dla każdej kwoty i sprawdzenia każdej monety dla każdego wpisu. Zwykła rekurencja bez memoizacji ma złożoność wykładniczą względem kwoty.

Czy podejście odgórne czy oddolne jest lepsze w problemie wydawania reszty?

Oba wykonują tyle samo pracy: O(amount × coins). Rekurencja odgórna może zagnieżdżać się na głębokość równą kwocie, co powoduje przepełnienie stosu wywołań przy 10^4 w kilku językach. Podejście oddolne wypełnia tabelę za pomocą pętli, więc nie ma ograniczenia głębokości i jest bezpieczniejszym wyborem na rozmowie kwalifikacyjnej.

def coinChange(coins, amount):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

coins = [2, 5, 10]
amount = 27

Oczekiwany wynik

Coin Change

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj każdą kombinację, używając rekurencji

Rekurencja z memoizacją

Programowanie dynamiczne od dołu dla kwot

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania