Contare i cammini su una griglia
Sommare i cammini da un angolo all’altro
Contare i cammini su una griglia è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il classico problema della griglia
Si parte dall'angolo in alto a sinistra di una griglia e si vuole raggiungere quello in basso a destra. Ogni passo va a destra o in basso. Quanti percorsi distinti esistono?
Perché la programmazione dinamica è adatta
Ogni cella può essere raggiunta dalla cella sopra oppure da quella a sinistra. Questa sovrapposizione è esattamente il motivo per cui questo è un problema di DP.
Definire lo stato
Indichiamo con dp[i][j] il numero di modi per raggiungere la cella (i, j) dalla partenza. Dare un nome chiaro allo stato è metà del lavoro.
La transizione
Si arriva soltanto dall'alto o da sinistra, quindi il conteggio è la loro somma. Questa è la transizione che guida l'intera tabella.
dp[i][j] = dp[i-1][j] + dp[i][j-1]Il caso base
Esiste esattamente un modo per raggiungere la cella di partenza: non fare nulla. Quindi dp[0][0] vale 1 prima di riempire qualsiasi altra cella.
dp[0][0] = 1Sui bordi c'è un solo percorso
Le celle della riga superiore o della colonna sinistra hanno un unico percorso rettilineo. Il loro conteggio è sempre 1, perché uno dei due vicini si trova fuori dalla griglia.
Costruire la tabella
Crei una tabella m per n inizializzata a zero. Stabilire subito le dimensioni mantiene puliti gli indici ed evita sorprese.
dp = [[0] * n for _ in range(m)]Riempire secondo l'ordine di lettura
Scorra prima le righe e poi le colonne, dall'alto verso il basso e da sinistra verso destra. Questo ordine garantisce che entrambi i vicini siano pronti prima di utilizzarli.
for i in range(m):
for j in range(n):
...La cella della risposta
Dopo il riempimento, il conteggio dei percorsi si trova nell'ultima cella. La risposta è dp[m-1][n-1], nell'angolo in basso a destra.
answer = dp[m-1][n-1]Risparmiare memoria con una sola riga
Ogni riga ha bisogno soltanto di quella precedente, quindi può mantenere una sola riga e aggiornarla sul posto. In questo modo la memoria scende a O(n).
row[j] += row[j-1]La scorciatoia matematica
Senza blocchi, la risposta è un coefficiente binomiale: si scelgono i passi totali che vanno verso il basso. La DP resta comunque preferibile quando compaiono ostacoli.
Verifica rapida
Sta riempiendo dp[i][j] per una cella interna libera. Quale formula è corretta?
Riepilogo: conteggio dei percorsi
Definisca dp come il numero di percorsi per raggiungere una cella, imposti dp[0][0] a 1 e sommi la cella sopra a quella a sinistra. L'angolo contiene la risposta. 🧭
Domande Frequenti
La lezione «Contare i cammini su una griglia» è gratuita?
Sì — il testo completo di «Contare i cammini su una griglia» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Contare i cammini su una griglia»?
Sommare i cammini da un angolo all’altro Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Contare i cammini su una griglia»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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
- Contare i cammini su una griglia
- Somma minima dei cammini con ostacoli
- Sottosequenza comune più lunga
- Distanza di edit passo dopo passo