Bottom-up-DP med tabulering
Omdan top-down-løsninger til iterative DP-tabeller, og reducer pladsforbruget fra O(n) til O(1), når kun de seneste poster er nødvendige.
Bottom-up-DP med tabulering er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 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.
Bottom-up-DP: Tabuleringsmetoden
Bottom-up-DP (tabulering) udfylder en tabel med svar på delproblemer, begyndende med de mindste delproblemer og byggende op mod svaret. I stedet for at rekurrere nedad og cache på vejen op beregner du iterativt fra bunden. Tabellen er typisk et 1D- eller 2D-array, hvor hver celle beregnes ud fra celler, der allerede er udfyldt. Det fjerner rekursion fuldstændigt — ingen kaldestak, ingen rekursionsgrænse og bedre 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 udfylder dp[0..n] fra venstre mod højre. dp[i] = dp[i-1] + dp[i-2] for i >= 2. Basistilfældene er dp[0] = 0 og dp[1] = 1, som gemmes direkte i arrayet. Tiden er O(n), og pladsen er O(n) for den fulde tabel. Når du ser, at dp[i] kun afhænger af de to seneste værdier, kan du reducere pladsen til O(1) med to variabler — dette er trinnet med pladsoptimering.
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-møntveksling
For møntveksling er bottom-up-tabellen dp[0..amount], hvor dp[i] = det mindste antal mønter, der skal bruges til at danne beløb i. Initialisér dp[0] = 0 (nul mønter for beløb nul) og dp[1..amount] = uendelighed. For hvert beløb i fra 1 til målet prøver du hver mønt: Hvis i >= coin, så er dp[i] = min(dp[i], 1 + dp[i - coin]). Svaret er dp[amount] eller -1, hvis værdien stadig er uendelighed.
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)) # 20Udfyldningsrækkefølge: Den afgørende indsigt
Udfyldningsrækkefølgen er kernen i bottom-up-DP. For enhver tilstand dp[i] skal alle tilstande, som den afhænger af, være beregnet først. For 1D-DP, hvor dp[i] afhænger af dp[i-1] og dp[i-2], skal du udfylde fra venstre mod højre. For 2D-DP, hvor dp[i][j] afhænger af dp[i-1][j] og dp[i][j-1], skal du udfylde række for række (fra top til bund, fra venstre mod højre). Tegn altid afhængighedspil, før du skriver kode, for at bekræfte udfyldningsrækkefølgen.
# 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: 2D-tabel
Bottom-up-tabellen for den længste fælles delsekvens er (m+1) × (n+1), hvor dp[i][j] = LCS for s1[:i] og s2[:j]. Basistilfælde: dp[0][j] = dp[i][0] = 0 (en tom streng har LCS-længden 0 med enhver streng). Udfyld række for række: Hvis s1[i-1] == s2[j-1], er dp[i][j] = 1 + dp[i-1][j-1]; ellers er dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Svaret er 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'Pladsoptimering: Rullende array
Mange 2D-DP-tabeller kan reduceres til 1D (eller 2 rækker), hvis du bemærker, at dp[i][j] kun afhænger af den aktuelle række og den forrige række. Behold to arrays: prev og curr, eller opdatér et enkelt array i den rigtige rækkefølge. For LCS afhænger dp[i][j] af dp[i-1][j], dp[i][j-1] og dp[i-1][j-1] — det er tilstrækkeligt kun at beholde den forrige række.
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-husrøveren
Bottom-up-løsningen til husrøveren udfylder dp[0..n-1], hvor dp[i] = den maksimale gevinst ved at røve husene fra 0 til og med i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]), og for i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Da dp[i] kun afhænger af de to seneste værdier, kan du straks pladsoptimere til O(1) med to variabler — et almindeligt mønster for 1D-DP med afhængigheder i to trin.
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])) # 12Mindste stisum i et gitter
Mindste stisum (LeetCode #64): find en sti fra øverste venstre hjørne til nederste højre hjørne, som minimerer summen af værdierne (du må kun gå mod højre eller ned). 2D-DP: dp[i][j] = den mindste sum for at nå celle (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Udfyld fra venstre mod højre og fra top til bund. Basistilfælde: dp[0][0] = grid[0][0], den første række udfyldes kun mod højre, og den første kolonne udfyldes kun nedad.
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Ændring af DP-tabellen på stedet
Når ekstra plads ikke er tilladt, kan du nogle gange ændre selve inputgitteret og bruge det som DP-tabellen. Ved mindste stisum overskriver du grid[i][j] med den mindste omkostning for at nå cellen. Det bruger O(1) ekstra plads, men ødelægger inputtet — nævn altid denne afvejning over for intervieweren, og bekræft, at den er acceptabel. Hvis inputtet skal bevares, skal du i stedet bruge metoden med et rullende 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))) # 7Sammenligning af oppefra-og-ned og nedefra-og-op ved møntveksling
Begge tilgange løser møntveksling optimalt, men de adskiller sig i praksis. Oppefra-og-ned er lettere at skrive og beregner kun de delproblemer, der faktisk kan nås. Nedefra-og-op beregner alle beløb fra 0 til målet, også dem, der ikke kan nås med de givne mønter, og som derfor forbliver uendelige. Ved sparsomme problemer med få tilgængelige tilstande er oppefra-og-ned mere effektivt; ved tætte problemer har nedefra-og-op mindre ekstraarbejde.
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)) # 2Unikke stier: Klassisk 2D-DP
Unikke stier (LeetCode #62) tæller antallet af stier fra øverste venstre hjørne til nederste højre hjørne i et m×n-gitter, hvor du kun må bevæge dig mod højre eller ned. Rekurrensen er enkel: dp[i][j] = dp[i-1][j] + dp[i][j-1] — stierne ovenfra plus stierne fra venstre. Basistilfælde: Hele den første række og den første kolonne har hver præcis 1 sti, fordi der kun er én retning at bevæge sig i. Denne 2D-DP udfyldes på O(mn)-tid og kan reduceres til O(n)-plads med en rullende række.
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)) # 28Hurtig kontrol
Afprøv din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du om: nedefra-og-op-DP med tabulering og hvordan du bestemmer udfyldningsrækkefølgen ud fra afhængighedspile, pladsoptimering ved hjælp af rullende arrays (O(mn) til O(n)) og sporing af to variable (O(n) til O(1)) samt nedefra-og-op-implementeringer af Fibonacci, møntveksling, LCS, husrøveren og mindste stisum. Derefter løser vi problemerne med møntveksling og trappen med minimale omkostninger fra ende til anden.
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 “Bottom-up-DP med tabulering” gratis?
Ja — hele teksten til “Bottom-up-DP med tabulering” 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 “Bottom-up-DP med tabulering”?
Omdan top-down-løsninger til iterative DP-tabeller, og reducer pladsforbruget fra O(n) til O(1), når kun de seneste poster er nødvendige. 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 3 af 4.
Hvor lang tid tager lektionen “Bottom-up-DP med tabulering”?
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
- Genkendelse af DP: overlappende delproblemer
- Top-down-DP med memoization
- Bottom-up-DP med tabulering
- Coin change og trappe med minimale omkostninger