DP illimitato e cambio di monete
Usare gli elementi un numero illimitato di volte
DP illimitato e cambio di monete è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Elementi illimitati
Nello zaino illimitato, ogni oggetto può essere preso tutte le volte che si desidera. Pensi alle monete in un distributore automatico, non a una pila fissa.
L'unica piccola modifica
Rispetto allo zaino 0/1, cambia soltanto la direzione del ciclo. Con elementi illimitati si percorre la capacità in avanti, dal valore più basso a quello più alto.
Il riutilizzo in avanti è essenziale
Procedendo in avanti, dp[w - coin] potrebbe già includere la stessa moneta. Questo riutilizzo intenzionale è ciò che permette di prenderla di nuovo.
Il problema del cambio
Il classico problema del coin change chiede il minor numero di monete la cui somma raggiunge un importo. È una DP con elementi illimitati che usa un minimo invece di un massimo.
Definire lo stato
Definisca dp[a] come il minor numero di monete necessario per ottenere l'importo a. Inizi impostando dp[0] = 0, perché per ottenere zero non servono monete.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Usare infinito per gli importi impossibili
Gli importi irraggiungibili iniziano con il valore infinito. Se un importo rimane infinito alla fine, nessuna combinazione di monete può formarlo.
La transizione
Per ogni moneta, provi a migliorare ogni importo che essa può raggiungere. Usi una moneta in più rispetto all'importo minore rimasto.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Perché l'ordine in avanti
Scorrere gli importi verso l'alto permette a dp[a - coin] di includere già questa moneta. È così che una singola moneta contribuisce più volte.
Contare invece i modi
Sostituisca minimo+1 con una somma per contare il numero di modi di ottenere ogni importo. Il ciclo sulle monete all'esterno evita di contare due volte gli stessi ordinamenti.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Leggere il risultato
La risposta si trova in dp[amount]. Nella versione con il minimo, un valore infinito significa che è impossibile formare l'obiettivo.
0/1 e illimitato
Ricordi l'unica differenza: la capacità percorsa all'indietro significa che ogni oggetto viene usato una volta, mentre quella percorsa in avanti consente un numero illimitato di utilizzi. La stessa tabella, con scansione opposta.
Verifica rapida
Verifichi che cosa rende illimitato il problema dello zaino.
Riepilogo
Ha invertito il ciclo procedendo in avanti per consentire il riutilizzo illimitato e ha costruito il problema del cambio usando il minimo per il minor numero di monete o la somma per il numero totale di modi. 💰
Domande Frequenti
La lezione «DP illimitato e cambio di monete» è gratuita?
Sì — il testo completo di «DP illimitato e cambio di monete» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «DP illimitato e cambio di monete»?
Usare gli elementi un numero illimitato di volte Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «DP illimitato e cambio di monete»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Knapsack 0/1: prendere o lasciare
- Knapsack ottimizzato nello spazio
- DP illimitato e cambio di monete
- Somma di sottoinsiemi e partizionamento