Minsta vägsumma med hinder
För över den bästa kostnaden mellan celler
Minsta vägsumma med hinder är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Från att räkna till att beräkna kostnad
Nu innehåller varje cell ett värde och Ni vill hitta den billigaste vägen till hörnet. Målet går från att räkna vägar till att minimera en kostnad.
Definiera tillståndet
Låt dp[i][j] vara den minsta totala kostnaden för att nå cell (i, j). Samma rutnät och samma förflyttningar, men nu följer vi summor i stället för antal.
Övergången
Ni väljer den billigare av de två inkommande grannarna och adderar sedan den aktuella cellen. Valet av min är kärnan i rekurrensen.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Markera hindren
Ett hinder är en cell som Ni inte kan stå på. Ge den kostnaden oändlighet, så blir ingen väg genom den någonsin billigast.
INF = float('inf')Blockera den på ett rent sätt
När rutnätet markerar en cell som blockerad sätter Ni bara dess dp till oändlighet och går vidare. Min-steget undviker den automatiskt.
if blocked(i, j):
dp[i][j] = INF
continueSkydda starten
Om själva startcellen är blockerad finns det ingen väg alls. Kontrollera det först, så att Ni inte returnerar en meningslös kostnad.
Initiera den första cellen
Startcellen har inga grannar att komma från, så dess kostnad är bara dess eget värde. Sätt dp[0][0] innan looparna körs.
dp[0][0] = grid[0][0]Hantera kanterna
Den översta raden kan bara nås från vänster och den vänstra kolumnen bara ovanifrån. Hantera dessa kanter så att Ni aldrig läser utanför rutnätet.
Oändlighet sprids
Att addera till oändlighet ger fortfarande oändlighet, så en helt avskärmad cell behåller sin INF-kostnad. Celler som inte kan nås visar det automatiskt.
Läs resultatet
Den minsta kostnaden finns i cellen längst ned till höger. Om värdet fortfarande är oändlighet finns det ingen giltig väg alls.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1När greedy misslyckas här
Om Ni alltid går mot den mindre grannen kan Ni hamna i en återvändsgränd. Endast fullständig DP garanterar den billigaste vägen globalt, inte en girig blick på nästa steg.
Snabb kontroll
Hur får Ni path-DP att undvika en blockerad cell utan att specialhantera varje granne?
Sammanfattning: billigaste vägen med hinder
Välj den billigare grannen och lägg till cellens värde, sätt blockerade celler till oändlighet och läs av hörnet. INF där betyder ingen väg. 🧱
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Minsta vägsumma med hinder” gratis?
Ja – hela texten till ”Minsta vägsumma med hinder” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Minsta vägsumma med hinder”?
För över den bästa kostnaden mellan celler Ni övar på Competitive Programming Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Minsta vägsumma med hinder”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Räkna vägar i ett rutnät
- Minsta vägsumma med hinder
- Längsta gemensamma delsekvens
- Editeringsavstånd steg för steg