Bottom-up-DP med tabulering
Gjør top-down-løsninger om til iterative DP-tabeller, og reduser plassen fra O(n) til O(1) når bare de siste oppføringene trengs.
Bottom-up-DP med tabulering er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 3 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.
Bottom-up-DP: Tabuleringsmetoden
Bottom-up-DP (tabulering) fyller en tabell med svar på delproblemer, fra de minste delproblemene og opp til svaret. I stedet for å rekurrere nedover og mellomlagre på veien opp beregner du iterativt nedenfra og opp. Tabellen er vanligvis en 1D- eller 2D-array der hver celle beregnes ut fra celler som allerede er fylt ut. Dette eliminerer rekursjon fullstendig – ingen kallstakk, ingen rekursjonsgrense og bedre cache-lokalitet.
# 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 ut dp[0..n] fra venstre mot høyre. dp[i] = dp[i-1] + dp[i-2] for i >= 2. Basistilfellene er dp[0] = 0 og dp[1] = 1, som lagres direkte i arrayet. Tiden er O(n), og plassen er O(n) for hele tabellen. Når du ser at dp[i] bare avhenger av de to siste verdiene, kan du redusere plassbruken til O(1) med to variabler – dette er trinnet for plassoptimalisering.
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 for Coin Change
For Coin Change er bottom-up-tabellen dp[0..amount], der dp[i] = minimumsantallet mynter for å lage beløpet i. Initialiser dp[0] = 0 (null mynter for beløpet null) og dp[1..amount] = infinity. For hvert beløp i fra 1 til målet prøver du hver mynt: hvis i >= coin, er dp[i] = min(dp[i], 1 + dp[i - coin]). Svaret er dp[amount], eller -1 hvis verdien fortsatt er infinity.
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)) # 20Utfyllingsrekkefølge: Den avgjørende innsikten
Utfyllingsrekkefølgen er selve kjernen i bottom-up-DP. For enhver tilstand dp[i] må alle tilstandene den avhenger av, være beregnet først. For 1D-DP der dp[i] avhenger av dp[i-1] og dp[i-2], fyller du ut fra venstre mot høyre. For 2D-DP der dp[i][j] avhenger av dp[i-1][j] og dp[i][j-1], fyller du ut rad for rad (ovenfra og ned, fra venstre mot høyre). Tegn alltid avhengighetspilene før du koder, slik at du kan bekrefte utfyllingsrekkefø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-tabell
Bottom-up-tabellen for Longest Common Subsequence er (m+1) × (n+1), der dp[i][j] = LCS-en til s1[:i] og s2[:j]. Basistilfellene er dp[0][j] = dp[i][0] = 0 (en tom streng har LCS 0 med hva som helst). Fyll ut rad for rad: 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'Plassoptimalisering: Rullerende array
Mange 2D-DP-tabeller kan reduseres til 1D (eller 2 rader) ved å observere at dp[i][j] bare avhenger av den gjeldende raden og den forrige raden. Behold to arrayer: prev og curr, eller oppdater én array i riktig rekkefølge. For LCS avhenger dp[i][j] av dp[i-1][j], dp[i][j-1] og dp[i-1][j-1] – det er tilstrekkelig å beholde bare den forrige 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 for House Robber
Bottom-up for House Robber fyller ut dp[0..n-1], der dp[i] = den maksimale fortjenesten ved å rane husene fra og med 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]). Siden dp[i] bare avhenger av de to siste verdiene, kan plassbruken umiddelbart optimaliseres til O(1) med to variabler – et vanlig mønster for 1D-DP med avhengigheter over to trinn.
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])) # 12Minimum Path Sum i et rutenett
Minimum Path Sum (LeetCode #64): Finn en vei fra øverst til venstre til nederst til høyre som minimerer summen av verdiene (du kan bare bevege deg mot høyre eller ned). 2D-DP: dp[i][j] = den minste summen for å nå celle (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Fyll ut fra venstre mot høyre og ovenfra og ned. Basistilfellet er dp[0][0] = grid[0][0]; den første raden fylles bare mot høyre, og den første kolonnen fylles bare nedover.
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+1Endre DP-tabellen på stedet
Når ekstra plass ikke er tillatt, kan du noen ganger endre selve input-rutenettet og bruke det som DP-tabell. For minimum path sum overskriver du grid[i][j] med den minste kostnaden for å nå cellen. Dette bruker O(1) ekstra plass, men ødelegger inndataene – nevn alltid denne avveiningen for intervjueren og bekreft at den er akseptabel. Hvis inndataene må bevares, bruker du rullerende array-metoden i stedet.
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 av top-down og bottom-up for myntveksling
Begge tilnærmingene løser myntveksling optimalt, men de fungerer forskjellig i praksis. Top-down er enklere å skrive og beregner bare delproblemer som faktisk kan nås. Bottom-up beregner alle beløp fra 0 til målbeløpet, også de som ikke kan nås med de angitte myntene (og som derfor forblir lik uendelig). For sparsomme problemer (få nåbare tilstander) er top-down mer effektivt. For tette problemer har bottom-up mindre 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)) # 2Unike stier: Klassisk 2D-DP
Unike stier (LeetCode #62) teller antallet stier fra øverst til venstre til nederst til høyre i et m×n-rutenett, der man bare kan bevege seg til høyre eller ned. Rekurrensen er enkel: dp[i][j] = dp[i-1][j] + dp[i][j-1] — stier ovenfra pluss stier fra venstre. Basistilfeller: Hele den første raden og den første kolonnen har nøyaktig 1 sti hver (det finnes bare én retning å bevege seg i). Denne 2D-DP-en fylles ut på O(mn) tid og kan reduseres til O(n) minne ved hjelp av en rullende 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)) # 28Kunnskapssjekk
Test forståelsen Deres av begrepene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen har De lært: bottom-up-DP med tabulering og hvordan utfyllingsrekkefølgen bestemmes av avhengighetspiler, minneoptimalisering ved hjelp av rullende arrayer (O(mn) til O(n)) og sporing med to variabler (O(n) til O(1)), samt bottom-up-implementasjoner av Fibonacci, myntveksling, LCS, husrøveren og minimumssti. Deretter skal vi løse problemene med myntveksling og trappetrinn med minimumskostnad fra start til slutt.
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 «Bottom-up-DP med tabulering» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Bottom-up-DP med tabulering», 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 «Bottom-up-DP med tabulering»?
Gjør top-down-løsninger om til iterative DP-tabeller, og reduser plassen fra O(n) til O(1) når bare de siste oppføringene trengs. 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 3 av 4.
Hvor lang tid tar leksjonen «Bottom-up-DP med tabulering»?
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
- Gjenkjenne DP: overlappende delproblemer
- Top-down-DP med memoisation
- Bottom-up-DP med tabulering
- Coin Change og trapp med minimale kostnader