Salita delle scale e combinazioni di monete
Creare da zero ricorrenze classiche unidimensionali
Salita delle scale e combinazioni 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.
Il problema Climbing Stairs
È possibile fare 1 o 2 passi alla volta. In quanti modi si raggiunge il passo n? Questa classica DP 1D è semplicemente la successione di Fibonacci sotto mentite spoglie.
Trovare la ricorrenza
Per arrivare al passo i, si deve provenire da i-1 o da i-2. Quindi dp[i] = dp[i-1] + dp[i-2], sommando entrambe le ultime mosse.
dp[i] = dp[i-1] + dp[i-2]Impostare i casi base
Esiste un modo per rimanere a terra e un modo per raggiungere il passo 1. Questi casi base inizializzano l'intera tabella.
dp[0], dp[1] = 1, 1Riempire e leggere la risposta
Scorra verso l'alto e l'ultima cella conterrà il conteggio. La soluzione completa è un piccolo ciclo di tabulazione.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Ridurre a due variabili
Servono solo gli ultimi due valori, quindi si può eliminare l'array. Questa versione con spazio O(1) è la preferita nelle gare.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bPassare alle combinazioni di monete
Dati i valori delle monete, conti i modi per ottenere l'importo A. Qui l'ordine non conta, quindi si contano le combinazioni, non le sequenze.
coins = [1, 2, 5]La tabella delle combinazioni
Definisca dp[x] come il numero di modi per formare x. Inizi con un modo per formare zero: l'insieme vuoto di monete.
dp = [0]*(A+1)
dp[0] = 1Mettere il ciclo sulle monete all'esterno
Metta il ciclo sulle monete all'esterno del ciclo sugli importi. Questo ordine conta ogni combinazione esattamente una volta, mai le permutazioni.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Combinazioni e permutazioni
Scambi l'ordine dei cicli e conterà invece i modi ordinati. Il solo annidamento dei cicli cambia il significato della risposta.
Variante del cambio con numero minimo di monete
Per ottenere il minor numero di monete, memorizzi un minimo anziché una somma. Inizializzi con infinito e prenda 1 più il miglior sottoproblema.
dp[x] = min(dp[x], dp[x-c] + 1)Un modello, molti volti
Scale e monete condividono la stessa struttura: ogni stato calcola una somma o un minimo su alcuni stati precedenti. Una volta riconosciuto questo schema, il codice viene da sé.
Verifica rapida
Nel conteggio delle combinazioni di monete, quale ordine dei cicli evita i duplicati?
Riepilogo: sommare le ultime mosse
Ora è in grado di risolvere il problema delle scale e il conteggio delle monete con una ricorrenza 1D. Ogni risposta somma alcuni stati precedenti e l'ordine dei cicli determina combinazioni o permutazioni.
Domande Frequenti
La lezione «Salita delle scale e combinazioni di monete» è gratuita?
Sì — il testo completo di «Salita delle scale e combinazioni 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 «Salita delle scale e combinazioni di monete»?
Creare da zero ricorrenze classiche unidimensionali 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 «Salita delle scale e combinazioni 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
- Memoization e tabulation a confronto
- Definire stato e transizione
- Salita delle scale e combinazioni di monete
- Sottosequenza crescente più lunga