Unike stier og minste stisum i rutenett
Fyll en 2D-DP-tabell for unike stier med og uten hindringer, og tilpass den deretter for å minimere summen av verdiene langs en sti.
Unike stier og minste stisum i rutenett er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 1 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Unique Paths i et rutenett
Unique Paths (LeetCode 62) spør: I et m×n-rutenett, hvor mange ulike stier går fra øverste venstre hjørne til nederste høyre hjørne hvis man bare kan bevege seg mot høyre eller ned? For et 3×7-rutenett er svaret 28. Hovedinnsikten er at enhver sti til cellen (i,j) må komme enten fra (i-1,j) (ovenfra) eller fra (i,j-1) (fra venstre), noe som gir en naturlig 2D-DP-formulering.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 22D-DP-tabell for Unique Paths
Definer dp[i][j] som antallet stier til cellen (i,j). Den første raden og den første kolonnen består bare av 1-ere (det finnes bare én måte å nå en celle i den øverste raden eller kolonnen lengst til venstre på). For de øvrige cellene gjelder: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Fyll ut tabellen rad for rad. Svaret er dp[m-1][n-1]. Tidskompleksitet: O(m×n), plass: O(m×n), som kan reduseres til O(n).
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)Plassoptimalisering til O(n)
Siden dp[i][j] bare avhenger av den gjeldende raden og raden før, kan hele 2D-tabellen erstattes med én 1D-array. Initialiser alle verdiene til 1, og oppdater deretter på stedet for hver rad: dp[j] += dp[j-1]. Etter behandling av rad i inneholder dp[j] verdien som var dp[i][j] i 2D-tabellen. Dette er et vanlig optimaliseringsmønster for 2D-DP-problemer.
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28Unique Paths II: Hindringer
Unique Paths II (LeetCode 63) legger til hindringer (celler merket med 1) i rutenettet. Alle stier gjennom en hindring er ugyldige, så dp[i][j] = 0 hvis obstacle[i][j] == 1. Ellers er rekurrensen den samme: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Hvis start- eller sluttcellen er blokkert, blir svaret umiddelbart 0. Initialiser basistilfellene nøye — når en 1 først dukker opp i den første raden eller kolonnen, er alle etterfølgende celler i den raden eller kolonnen 0.
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2Problem med minste stisum
Minimum Path Sum (LeetCode 64) spør: Gitt et m×n-rutenett fylt med ikke-negative heltall, finn stien fra øverst til venstre til nederst til høyre som minimerer summen av alle tallene langs stien (med bevegelser bare mot høyre eller ned). I [[1,3,1],[1,5,1],[4,2,1]] gir for eksempel stien 1→3→1→1→1 summen 7. DP-tilstanden er den samme som for Unique Paths, men rekurrensen bruker nå minimum i stedet for addisjon.
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)DP-implementasjon for minste stisum
Definer dp[i][j] som den laveste kostnaden for å nå cellen (i,j). Basistilfelle: dp[0][0] = grid[0][0]. Første rad: dp[0][j] = dp[0][j-1] + grid[0][j] (den eneste veien kommer fra venstre). Første kolonne: dp[i][0] = dp[i-1][0] + grid[i][0] (den eneste veien kommer ovenfra). Generelt: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Dette er en direkte anvendelse av optimalitetsprinsippet.
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7Minste stisum med oppdatering på stedet
Hvis det er tillatt å endre input-rutenettet, kan det oppdateres på stedet for å unngå å allokere en separat DP-tabell. Dette reduserer den ekstra plassen til O(1) utover inputen. I intervjuer spør man noen ganger om denne optimaliseringen — avklar om det er tillatt å endre inputen, før dette gjøres. Hvis ikke gir trikset med en 1D-array som rulles gjennom radene, O(n) plass uten å endre inputen.
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Minimal stisum i en trekant
Triangle (LeetCode 120) spør etter den minste stisummen fra toppen til bunnen av en trekantarray, der hvert trinn går til et tilstøtende tall i raden under. Bottom-up-DP er den ryddigste løsningen: Start i raden nest nederst, og legg for hver celle til minimumet av de to cellene rett nedenfor. Da slipper man å holde styr på startindekser, og svaret flyttes naturlig opp til toppen.
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)Rutenett-DP i Dungeon Game
Dungeon Game (LeetCode 174) spør etter den minste starthelsen som kreves for å redde en prinsesse i nederste høyre hjørne av et rutenett med negative celler (skade) og positive celler (helbredelse). Man må bevege seg mot høyre eller ned. Trikset er å fylle ut DP-tabellen baklengs (fra nederst til høyre til øverst til venstre) og beregne hvor mye helse som kreves i hver celle. I hver celle gjelder: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Helsen må alltid være minst 1.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7Sammenligning av rutenett-DP-problemer
Rutenett-DP-problemer har samme struktur, men skiller seg i fylleretning og overgangsoperasjon: Unique Paths bruker addisjon (tell alle måter). Min Path Sum bruker minimum (optimaliser). Dungeon Game fylles baklengs (helse som kreves basert på det som kommer senere). Når man møter et nytt rutenett-DP-problem, bør man spørre seg: (1) Hva representerer hver celle? (2) I hvilken retning fyller man ut? (3) Hvilken operasjon kombinerer naboene? Svarene på disse tre spørsmålene avdekker hele løsningen.
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')Kompleksitetsoppsummering for rutenett-DP
Alle rutenett-DP-problemene her bruker O(m×n) tid. Plassen varierer fra O(m×n) for en full tabell til O(n) med en 1D-array som rulles gjennom radene, og O(1) ekstra plass når rutenettet kan endres på stedet. I intervjuer bør man nevne O(n)-optimaliseringen etter å ha presentert O(m×n)-løsningen — det viser forståelse for avveiningene. For alle problemene bør man også vurdere om det finnes en grådig snarvei, slik som den matematiske formelen for Unique Paths.
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7Hurtigsjekk
Test forståelsen av konseptene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte man at: Unique Paths fyller ut en 2D-tabell med dp[i][j] = dp[i-1][j] + dp[i][j-1] og kan beregnes i O(1) ved hjelp av kombinatorikk, Min Path Sum bruker den samme strukturen, men erstatter addisjon med min for å finne den optimale stikostnaden, og alle rutenett-DP-problemer følger mønsteret med å definere en tilstand per celle og velge en overgangsoperator (sum, min, maks). Neste tema er Longest Common Subsequence ved hjelp av 2D-DP på to sekvenser.
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Unike stier og minste stisum i rutenett» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Unike stier og minste stisum i rutenett», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «Unike stier og minste stisum i rutenett»?
Fyll en 2D-DP-tabell for unike stier med og uten hindringer, og tilpass den deretter for å minimere summen av verdiene langs en sti. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Unike stier og minste stisum i rutenett»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Unike stier og minste stisum i rutenett
- Lengste felles delsekvens
- Edit distance (Levenshtein)
- Plassoptimalisering for 2D-DP