Coin Change

Q: Qual è la complessità temporale di Coin Change?

La soluzione con programmazione dinamica richiede un tempo O(amount × coins) e uno spazio O(amount) : una voce della tabella per ogni importo e ogni moneta controllata per ciascuna voce. La ricorsione semplice senza memoizzazione ha una complessità esponenziale rispetto all'importo.

Q: È meglio l’approccio top-down o bottom-up per il problema del resto?

Entrambi svolgono lo stesso lavoro O(amount × coins) . La ricorsione top-down può annidarsi fino all'importo, superando la capacità dello stack delle chiamate con 10^4 in diversi linguaggi. L'approccio bottom-up riempie la tabella con un ciclo, quindi non ha limiti di profondità ed è la scelta più sicura in un colloquio.

MedioProgrammazione dinamica

+10

Ti viene fornita una lista coins di diversi valori di monete e un amount obiettivo. Puoi usare ogni valore di moneta tutte le volte che vuoi. Restituisci il numero minimo di monete i cui valori sommati danno esattamente amount, oppure -1 se nessuna combinazione di monete permette di raggiungerlo. Un importo pari a 0 richiede 0 monete.

Funzione

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

coinsinteger-array: i diversi valori delle monete, ciascuno utilizzabile un numero qualsiasi di volte
amountinteger: il totale esatto da pagare
Restituisceinteger: il minor numero di monete necessario, oppure -1 quando non è possibile ottenere l’importo

Vincoli

1 ≤ coins.length ≤ 12
1 ≤ coins[i] ≤ 10⁴
0 ≤ amount ≤ 10⁴
Tutti i valori delle monete sono diversi.

Esempi

Input: coins = [2, 5, 10]amount = 27
Output: 4
Spiegazione: 10 + 10 + 5 + 2 fanno 27 con quattro monete. Con tre monete non ci riesci: 27 è dispari, quindi te ne serve esattamente una da 5, e le altre due sommano al massimo 20, meno di 22.

Per approfondire

Riesci a contare quante combinazioni diverse di monete danno come somma amount, invece di trovare il minor numero di monete?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Scegliere la moneta più grande che ci sta non funziona: con monete da 1, 3 e 4, il valore 6 viene pagato con 4 + 1 + 1, mentre 3 + 3 richiede due monete. Il numero minimo di monete per un importo dipende solo dal numero minimo di monete per importi più piccoli, quindi risolvi ogni importo da 0 a amount una sola volta.

Prova ogni combinazione con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

Se l’ultima moneta che paghi vale c, le monete pagate prima coprono remaining - c nel modo più economico possibile. Quindi fewest(remaining) è uno in più del miglior fewest(remaining - c) tra tutte le monete utilizzabili. Questo prova ogni sequenza di monete che non supera l’importo, quindi non può tralasciare quella migliore.

Ricalcola più volte gli stessi importi. Con monete da 2, 5 e 10, l’importo 27 raggiunge 15 dopo aver pagato 10 + 2, 2 + 10, 5 + 5 + 2 e in molti altri ordini, e calcola 15 da zero ogni volta. Il numero di chiamate cresce in modo esponenziale rispetto all’importo.

Algoritmo

Scrivi una funzione di supporto fewest(remaining) che restituisce il minor numero di monete per remaining, oppure -1 se nessuna combinazione funziona.
Se remaining è 0, restituisci 0.
Per ogni moneta non superiore a remaining, chiama la funzione di supporto con ciò che resta dopo aver pagato quella moneta.
Conserva il risultato più piccolo diverso da -1, più uno per la moneta pagata.
Restituisci quel conteggio, oppure -1 se nessuna moneta ha portato a una soluzione. La risposta è 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)

Ricorsione con memoizzazione

Corretto, ma non termina sui test più grandi

Intuizione

La ricorsione chiede informazioni solo sugli importi da 0 a amount. Memorizza ogni risposta in un array la prima volta che la calcoli e restituisci il valore memorizzato quando quell'importo si ripresenta. Ogni importo viene risolto una sola volta con un ciclo sulle monete: O(amount × coins) operazioni.

Le chiamate continuano comunque ad annidarsi di un livello per ogni moneta pagata. Con una moneta del valore di 1, si possono raggiungere 10^4 livelli, più di quanti ne consenta lo stack delle chiamate predefinito in molti linguaggi.

Algoritmo

Crea un array memo con spazio per ogni importo da 0 a amount, contenente un marcatore che indica che non è ancora stato calcolato.
In fewest(remaining), restituisci 0 per 0 e restituisci memo[remaining] se contiene già una risposta.
Altrimenti prova ogni moneta che ci sta, come nella ricorsione semplice, e conserva il risultato più piccolo più uno.
Salva il risultato, incluso -1, in memo[remaining] prima di restituirlo.
Restituisci 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)

Programmazione dinamica bottom-up sugli importi

Intuizione

Riempi una tabella fewest partendo da 0. Quando raggiungi un totale t, tutti i totali inferiori sono risolti, quindi fewest[t] è uno in più del valore più piccolo di fewest[t-c] tra le monete c che ci stanno.

I totali che non si possono raggiungere con alcuna combinazione di monete contengono il marcatore amount + 1. Ogni moneta vale almeno 1, quindi una risposta valida non usa mai più di amount monete e il marcatore perde ogni confronto. Un ciclo sostituisce la ricorsione, quindi la profondità dello stack delle chiamate non è mai rilevante.

Algoritmo

Crea fewest con amount + 1 elementi, tutti impostati al marcatore amount + 1, e imposta fewest[0] a 0.
Per ogni totale t da 1 a amount, esamina ogni moneta c per cui c ≤ t.
Se fewest[t-c] + 1 è minore di fewest[t], memorizzalo in fewest[t].
Dopo il ciclo, restituisci -1 se fewest[amount] contiene ancora il marcatore; altrimenti restituisci 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

Trappole e casi limite

Prendere prima la moneta di valore più alto. Con le monete 3 e 5 e un importo di 9, paga 5 e 3, si blocca a 1 e restituisce -1, mentre 3 + 3 + 3 funziona.
Usare l'intero più grande come marcatore. Aggiungervi 1 causa un overflow, generando un numero negativo che poi vince ogni confronto. Usa amount + 1.
Aggiungere 1 a un vicolo cieco. Un ramo che restituisce -1, più la moneta pagata, dà 0 e vince ogni confronto. Salta i risultati -1.
Ricorrere per amount livelli. Con una moneta del valore di 1 e un importo pari a 10^4, Python si arresta al limite predefinito di 1000 livelli, e anche JavaScript, Dart, Ruby e R esauriscono lo stack.
Leggere fewest[t-c] per una moneta più grande di t, prima dell'inizio della tabella.

Domande frequenti3

Perché l’approccio greedy non funziona per il problema del resto?

Prendere la moneta più grande che ci sta è una scelta sicura solo per alcuni sistemi di monete, come la maggior parte delle valute reali. Con monete da 1, 3 e 4, paga 6 con tre monete invece che con due, e con monete da 3 e 5 non può pagare 9 affatto. La programmazione dinamica confronta ogni scelta, quindi nessun sistema di monete può ingannarla.

Qual è la complessità temporale di Coin Change?

La soluzione con programmazione dinamica richiede un tempo O(amount × coins) e uno spazio O(amount): una voce della tabella per ogni importo e ogni moneta controllata per ciascuna voce. La ricorsione semplice senza memoizzazione ha una complessità esponenziale rispetto all'importo.

È meglio l’approccio top-down o bottom-up per il problema del resto?

Entrambi svolgono lo stesso lavoro O(amount × coins). La ricorsione top-down può annidarsi fino all'importo, superando la capacità dello stack delle chiamate con 10^4 in diversi linguaggi. L'approccio bottom-up riempie la tabella con un ciclo, quindi non ha limiti di profondità ed è la scelta più sicura in un colloquio.

def coinChange(coins, amount):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

Coin Change

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni combinazione con la ricorsione

Ricorsione con memoizzazione

Programmazione dinamica bottom-up sugli importi

Trappole e casi limite

Domande frequenti3

Problemi simili