Somma minima dei cammini con ostacoli
Portare il costo migliore attraverso le celle
Somma minima dei cammini con ostacoli è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 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.
Dal conteggio al costo
Ora ogni cella contiene un valore e si vuole trovare il percorso meno costoso fino all'angolo. L'obiettivo passa dal conteggio dei percorsi alla minimizzazione di un costo.
Definire lo stato
Indichiamo con dp[i][j] il costo totale minimo per raggiungere la cella (i, j). La griglia e i movimenti sono gli stessi, ma ora si tracciano somme invece di conteggi.
La transizione
Si sceglie il più economico tra i due vicini da cui si può arrivare, poi si aggiunge la cella corrente. Questa scelta con min è il cuore della ricorrenza.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Contrassegnare gli ostacoli
Un ostacolo è una cella in cui non ci si può fermare. Le si assegni un costo infinito, così ogni percorso che la attraversa non potrà mai essere il minimo.
INF = float('inf')Bloccare in modo pulito
Quando la griglia indica che una cella è bloccata, imposti semplicemente il suo dp a infinito e prosegua. Il passaggio con min la eviterà automaticamente.
if blocked(i, j):
dp[i][j] = INF
continueProteggere la partenza
Se la cella di partenza è bloccata, non esiste alcun percorso. Verifichi questo per primo, così non restituirà un costo privo di significato.
Inizializzare la prima cella
La partenza non ha vicini da cui arrivare, quindi il suo costo è semplicemente il proprio valore. Imposti dp[0][0] prima dell'esecuzione dei cicli.
dp[0][0] = grid[0][0]Gestire i bordi
La riga superiore riceve valori soltanto da sinistra e la colonna sinistra soltanto dall'alto. Gestisca questi bordi per non leggere fuori dalla griglia.
L'infinito si propaga
Sommandovi un valore, l'infinito resta infinito, quindi una cella completamente isolata conserva il costo INF. Le celle irraggiungibili si segnalano automaticamente.
Leggere il risultato
Il costo minimo si trova nella cella in basso a destra. Se quel valore è ancora infinito, non esiste alcun percorso valido.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1Quando l'approccio greedy fallisce
Spostarsi sempre verso il vicino più piccolo può condurre a un vicolo cieco. Soltanto la DP garantisce il percorso globalmente meno costoso, non una scelta greedy basata sul solo passo successivo.
Verifica rapida
Come si può fare in modo che la DP dei percorsi eviti una cella bloccata senza gestire separatamente ogni vicino?
Riepilogo: percorso minimo con ostacoli
Scelga il vicino più economico, aggiunga il valore della cella, imposti le celle bloccate a infinito e legga l'angolo. INF in quella posizione significa nessun percorso. 🧱
Domande Frequenti
La lezione «Somma minima dei cammini con ostacoli» è gratuita?
Sì — il testo completo di «Somma minima dei cammini con ostacoli» è 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 «Somma minima dei cammini con ostacoli»?
Portare il costo migliore attraverso le celle 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 2 di 4.
Quanto tempo richiede la lezione «Somma minima dei cammini con ostacoli»?
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