Bottom-up-DP med tabellutfyllnad
Konvertera top-down-lösningar till iterativa DP-tabeller och minska utrymmet från O(n) till O(1) när bara de senaste posterna behövs.
Bottom-up-DP med tabellutfyllnad är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 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 Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Bottom-up-DP: tabelleringsmetoden
Bottom-up-DP (tabellering) fyller i en tabell med svar på delproblem, från de minsta delproblemen och upp till svaret. I stället för att rekursivt gå nedåt och cacha på vägen upp beräknar Ni iterativt från grunden. Tabellen är vanligtvis en endimensionell eller tvådimensionell array där varje cell beräknas utifrån celler som redan har fyllts i. Detta eliminerar rekursion helt — ingen anropsstack, ingen rekursionsgräns och bättre cachelokalitet.
# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)
# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')Bottom-up-Fibonacci
Bottom-up-Fibonacci fyller i dp[0..n] från vänster till höger. dp[i] = dp[i-1] + dp[i-2] för i >= 2. Basfallen är dp[0] = 0 och dp[1] = 1, som lagras direkt i arrayen. Tiden är O(n) och minnesåtgången är O(n) för hela tabellen. När Ni ser att dp[i] bara beror på de två senaste värdena kan Ni minska minnesåtgången till O(1) med två variabler — detta är steget med minnesoptimering.
def fib_bottom_up(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0 # base case
dp[1] = 1 # base case
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Space-optimised to O(1):
def fib_optimised(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_optimised(50)) # 12586269025Bottom-up Coin Change
För coin change är bottom-up-tabellen dp[0..amount], där dp[i] = minsta antalet mynt för att skapa beloppet i. Initiera dp[0] = 0 (noll mynt för beloppet noll) och dp[1..amount] = oändlighet. För varje belopp i från 1 till target provar Ni varje mynt: om i >= coin gäller dp[i] = min(dp[i], 1 + dp[i - coin]). Svaret är dp[amount], eller -1 om värdet fortfarande är oändlighet.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin: # can use this coin
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2: (5+6)
print(coin_change([2], 3)) # -1: impossible
print(coin_change([1, 2, 5], 11)) # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249)) # 20Fyllnadsordningen: den avgörande insikten
Fyllnadsordningen är kärnan i bottom-up-DP. För varje tillstånd dp[i] måste alla tillstånd som det beror på ha beräknats först. För endimensionell DP där dp[i] beror på dp[i-1] och dp[i-2] fyller Ni i från vänster till höger. För tvådimensionell DP där dp[i][j] beror på dp[i-1][j] och dp[i][j-1] fyller Ni i rad för rad (uppifrån och ned, från vänster till höger). Rita alltid beroendepilarna innan Ni kodar för att bekräfta fyllnadsordningen.
# Fill order examples:
# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n
# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.
# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems
print('Draw dependencies first, then determine fill order')Bottom-up-LCS: tvådimensionell tabell
Bottom-up-tabellen för Longest Common Subsequence är (m+1) × (n+1), där dp[i][j] = LCS för s1[:i] och s2[:j]. Basfall: dp[0][j] = dp[i][0] = 0 (en tom sträng har LCS 0 med vad som helst). Fyll i rad för rad: om s1[i-1] == s2[j-1] gäller dp[i][j] = 1 + dp[i-1][j-1]; annars gäller dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Svaret är dp[m][n].
def lcs_bottom_up(s1, s2):
m, n = len(s1), len(s2)
# (m+1) x (n+1) table, initialised to 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]: # characters match
dp[i][j] = 1 + dp[i-1][j-1]
else: # skip one character
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs_bottom_up('abcde', 'ace')) # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB')) # 4: 'BCAB' or 'BDAB'Minnesoptimering: rullande array
Många tvådimensionella DP-tabeller kan reduceras till en dimension (eller två rader) genom att observera att dp[i][j] bara beror på den aktuella raden och den föregående raden. Behåll två arrayer: prev och curr, eller uppdatera en enda array i rätt ordning. För LCS beror dp[i][j] på dp[i-1][j], dp[i][j-1] och dp[i-1][j-1] — det räcker att behålla den föregående raden.
def lcs_space_optimised(s1, s2):
m, n = len(s1), len(s2)
# Keep only one row (previous row state)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = 1 + prev[j-1] # dp[i-1][j-1]
else:
curr[j] = max(prev[j], curr[j-1]) # dp[i-1][j] and dp[i][j-1]
prev = curr
return prev[n]
print(lcs_space_optimised('abcde', 'ace')) # 3
# Space: O(n) instead of O(mn)Bottom-up House Robber
Bottom-up-lösningen för House Robber fyller i dp[0..n-1], där dp[i] = den största vinsten från att råna husen 0 till och med i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) och för i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Eftersom dp[i] bara beror på de två senaste värdena kan detta omedelbart minnesoptimeras till O(1) med två variabler — ett vanligt mönster för endimensionell DP med beroenden två steg bakåt.
def rob_bottom_up(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
# Full table version: O(n) space
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
def rob_optimised(nums):
# O(1) space: only need last two values
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12Minsta vägsumma i ett rutnät
Minimum Path Sum (LeetCode #64): hitta en väg från det övre vänstra hörnet till det nedre högra som minimerar summan av värdena (Ni får bara gå åt höger eller nedåt). Tvådimensionell DP: dp[i][j] = den minsta summan för att nå cellen (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Fyll i från vänster till höger och uppifrån och ned. Basfall: dp[0][0] = grid[0][0]; den första raden fylls endast åt höger och den första kolumnen endast nedåt.
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
# Fill first row (can only come from left)
for c in range(1, cols):
dp[0][c] = dp[0][c-1] + grid[0][c]
# Fill first column (can only come from above)
for r in range(1, rows):
dp[r][0] = dp[r-1][0] + grid[r][0]
# Fill rest of the table
for r in range(1, rows):
for c in range(1, cols):
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
return dp[rows-1][cols-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7: 1+3+1+1+1Ändra DP-tabellen på plats
När extra minnesutrymme inte är tillåtet kan Ni ibland ändra själva indatarutnätet och använda det som DP-tabell. För minimum path sum skriver Ni över grid[i][j] med den minsta kostnaden för att nå den cellen. Detta använder O(1) extra minnesutrymme men förstör indata — nämn alltid denna avvägning för intervjuaren och bekräfta att den är acceptabel. Om indatan måste bevaras använder Ni i stället en lösning med rullande array.
def min_path_sum_inplace(grid):
rows, cols = len(grid), len(grid[0])
# Modify grid in-place (O(1) extra space, destroys input)
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue # starting cell
elif r == 0:
grid[r][c] += grid[r][c-1] # first row
elif c == 0:
grid[r][c] += grid[r-1][c] # first column
else:
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
return grid[rows-1][cols-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Jämförelse mellan top-down och bottom-up vid myntväxling
Båda angreppssätten löser myntväxling optimalt, men de skiljer sig i praktiken. Top-down är renare att skriva och beräknar bara delproblem som faktiskt kan nås. Bottom-up beräknar alla belopp från 0 till målet, även sådana som inte kan nås med de givna mynten (och som förblir oändliga). För glesa problem (med få nåbara tillstånd) är top-down effektivare; för täta problem har bottom-up lägre overhead.
import functools
# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0: return 0
if rem < 0: return float('inf')
return 1 + min(dp(rem - c) for c in coins)
r = dp(amount)
return r if r != float('inf') else -1
# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_top([1,5,6,9], 11)) # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2Unika vägar: klassisk 2D-DP
Unika vägar (LeetCode #62) räknar antalet vägar från det övre vänstra hörnet till det nedre högra hörnet i ett m×n-rutnät, där man endast får gå åt höger eller nedåt. Rekurrensen är enkel: dp[i][j] = dp[i-1][j] + dp[i][j-1] — vägarna från ovan plus vägarna från vänster. Basfall: hela den första raden och den första kolumnen har exakt 1 väg vardera (det finns bara en riktning att gå i). Denna 2D-DP fyller tabellen på O(mn)-tid och kan minskas till O(n) minnesutrymme med en rullande rad.
def unique_paths(m, n):
# dp[i][j] = number of paths to reach cell (i,j)
dp = [[1] * n for _ in range(m)]
# Base: first row and first column are all 1
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, 2)) # 3
# O(n) space rolling row:
def unique_paths_opt(m, n):
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[n-1]
print(unique_paths_opt(3, 7)) # 28Snabbtest
Testa dina kunskaper om begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen lärde du dig: bottom-up-DP med tabulering och hur fyllnadsordningen bestäms av beroendepilarna, minnesoptimering med rullande arrayer (från O(mn) till O(n)) och spårning med två variabler (från O(n) till O(1)), samt bottom-up-implementationer av Fibonacci, myntväxling, LCS, House Robber och minsta vägsumma. Härnäst löser vi problemen med myntväxling och trappor med minsta kostnad från början till slut.
Lär dig Förberedelse inför kodningsintervjuer 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
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Bottom-up-DP med tabellutfyllnad” gratis?
Ja – hela texten till ”Bottom-up-DP med tabellutfyllnad” 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 Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Bottom-up-DP med tabellutfyllnad”?
Konvertera top-down-lösningar till iterativa DP-tabeller och minska utrymmet från O(n) till O(1) när bara de senaste posterna behövs. Ni övar på Förberedelse inför kodningsintervjuer 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 Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer 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 3 av 4.
Hur lång tid tar lektionen ”Bottom-up-DP med tabellutfyllnad”?
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 Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-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
- Identifiera DP: överlappande delproblem
- Top-down-DP med memoisation
- Bottom-up-DP med tabellutfyllnad
- Coin change och trappa med minimal kostnad