Unikke stier og minimal stisum i grids
Udfyld en 2D-DP-tabel for unikke stier med og uden forhindringer, og tilpas den derefter til at minimere summen af værdier langs en sti.
Unikke stier og minimal stisum i grids er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Unikke stier på et gitter
Unikke stier (LeetCode 62) spørger: I et m×n-gitter, hvor mange forskellige veje går fra øverste venstre hjørne til nederste højre hjørne, hvis du kun må bevæge dig mod højre eller ned? For et gitter på 3×7 er svaret 28. Den centrale indsigt er, at enhver vej til cellen (i,j) enten må komme fra (i-1,j) (ovenfra) eller (i,j-1) (fra venstre), hvilket giver 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-tabel for unikke stier
Definér dp[i][j] som antallet af veje til cellen (i,j). Den første række og den første kolonne består kun af 1-taller (der er kun én måde at nå enhver celle i den øverste række eller den venstre kolonne på). For andre celler gælder: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Udfyld tabellen række for række; svaret er dp[m-1][n-1]. Tidskompleksitet: O(m×n), plads: O(m×n), som kan reduceres 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)Pladsoptimering til O(n)
Da dp[i][j] kun afhænger af den aktuelle række og den foregående række, kan du erstatte den fulde 2D-tabel med et enkelt 1D-array. Initialisér alle værdier til 1, og opdatér derefter arrayet på stedet for hver række: dp[j] += dp[j-1]. Efter behandling af række i indeholder dp[j] den værdi, som var dp[i][j] i 2D-tabellen. Dette er et almindeligt optimeringsmø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)) # 28Unikke stier II: forhindringer
Unikke stier II (LeetCode 63) tilføjer forhindringer (celler markeret med 1) til gitteret. Enhver vej gennem en forhindring er ugyldig, så dp[i][j] = 0, hvis obstacle[i][j] == 1. Ellers er rekursionen den samme: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Hvis start- eller slutcellen er blokeret, er svaret straks 0. Initialisér basistilfældene omhyggeligt — så snart der optræder et 1-tal i den første række eller kolonne, er alle efterfølgende celler i den pågældende række eller kolonne 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)) # 2Problemet med minimal stisum
Minimal stisum (LeetCode 64) spørger: Givet et m×n-gitter udfyldt med ikke-negative heltal, find den vej fra øverste venstre til nederste højre, der minimerer summen af alle tal på vejen (hvor du kun må bevæge dig mod højre eller ned). I [[1,3,1],[1,5,1],[4,2,1]] giver vejen 1→3→1→1→1 for eksempel summen 7. DP-tilstanden er den samme som for unikke stier, men rekursionen bruger nu minimum i stedet for addition.
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)Implementering af DP til minimal stisum
Definér dp[i][j] som den minimale omkostning for at nå cellen (i,j). Basistilfælde: dp[0][0] = grid[0][0]. Første række: dp[0][j] = dp[0][j-1] + grid[0][j] (den eneste vej kommer fra venstre). Første kolonne: dp[i][0] = dp[i-1][0] + grid[i][0] (den eneste vej kommer ovenfra). Generelt gælder: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Dette er en direkte omsætning af optimalitetsprincippet.
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)) # 7Minimal stisum på stedet
Hvis du må ændre inputgitteret, kan du opdatere det på stedet for at undgå at allokere en separat DP-tabel. Det reducerer den ekstra plads til O(1) ud over inputtet. Interviewere spørger nogle gange om denne optimering — afklar, om det er tilladt at ændre inputtet, før du gør det. Hvis ikke, giver tricket med et rullende 1D-array O(n)-plads uden at ændre inputtet.
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
Trekant (LeetCode 120) spørger efter den minimale stisum fra toppen til bunden af et trekantarray, hvor hvert trin går til et tilstødende tal i rækken nedenunder. Bottom-up-DP er den enkleste løsning: Start ved den næstsidste række, og læg for hver celle minimum af de to celler direkte nedenunder til. Det undgår at holde styr på startindekser og løfter naturligt svaret op 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)Gitter-DP i et fangehul
Fangehulsspillet (LeetCode 174) spørger efter den minimale starthelbredsmængde, der kræves for at redde en prinsesse i nederste højre hjørne af et gitter med negative celler (skade) og positive celler (helbredelse). Du skal bevæge dig mod højre eller ned. Tricket er at udfylde DP-tabellen baglæns (fra nederste højre til øverste venstre) og beregne det minimale helbred, der kræves i hver celle. I hver celle gælder: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Helbredet skal altid være mindst 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 af gitter-DP-problemer
Gitter-DP-problemer har den samme struktur, men adskiller sig i udfyldningsretning og overgangsoperation: Unikke stier bruger addition (tæl alle måder). Minimal stisum bruger minimum (optimér). Fangehulsspillet udfyldes baglæns (det helbred, der kræves fra fremtidige celler). Når du møder et nyt gitter-DP-problem, så spørg dig selv: (1) Hvad repræsenterer hver celle? (2) I hvilken retning udfylder jeg tabellen? (3) Hvilken operation kombinerer naboerne? Svarene på disse tre spørgsmål afslører 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')Kompleksitetsopsummering for gitter-DP
Alle gitter-DP-problemerne her kører med O(m×n)-tidskompleksitet. Pladsforbruget går fra O(m×n) for en fuld tabel ned til O(n) med et rullende 1D-array og O(1) ekstra plads, når gitteret kan ændres på stedet. Til jobsamtaler bør du nævne O(n)-pladsoptimeringen efter at have præsenteret O(m×n)-løsningen — det viser, at du er opmærksom på afvejninger. Overvej også for alle problemer, om der findes en grådig genvej (som den matematiske formel for unikke stier).
# 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)) # 7Hurtigt tjek
Test din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion har du lært, at Unikke stier udfylder en 2D-tabel med dp[i][j] = dp[i-1][j] + dp[i][j-1] og kan beregnes i O(1) med kombinatorik, at Minimal stisum bruger den samme struktur, men erstatter addition med min for at finde den optimale stiomkostning, og at alle gitter-DP-problemer følger mønsteret med at definere en tilstand pr. celle og vælge en overgangsoperator (sum, min, max). Nu går vi videre med den længste fælles delsekvens ved hjælp af 2D-DP på to sekvenser.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Unikke stier og minimal stisum i grids” gratis?
Ja — hele teksten til “Unikke stier og minimal stisum i grids” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Unikke stier og minimal stisum i grids”?
Udfyld en 2D-DP-tabel for unikke stier med og uden forhindringer, og tilpas den derefter til at minimere summen af værdier langs en sti. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Unikke stier og minimal stisum i grids”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Unikke stier og minimal stisum i grids
- Længste fælles delsekvens
- Edit distance (Levenshtein)
- Pladsoptimering for 2D-DP