DP z dołu do góry z tabulacją
Przekształcą Państwo rozwiązania top-down w iteracyjne tablice DP i zmniejszą zużycie pamięci z O(n) do O(1), gdy potrzebnych jest tylko kilka ostatnich wpisów.
DP z dołu do góry z tabulacją to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
DP od dołu: podejście tabulacji
DP od dołu (tabulacja) wypełnia tabelę wyników podproblemów, zaczynając od najmniejszych podproblemów i stopniowo dochodząc do rozwiązania. Zamiast schodzić rekurencyjnie w dół i zapisywać wyniki podczas powrotu, wyniki oblicza się iteracyjnie od podstaw. Tabela jest zazwyczaj tablicą jednowymiarową lub dwuwymiarową, w której każda komórka jest obliczana na podstawie wcześniej wypełnionych komórek. Eliminuje to rekurencję — nie ma stosu wywołań ani limitu rekurencji, a lokalność odwołań do pamięci podręcznej jest lepsza.
# 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')Fibonacci od dołu
DP od dołu dla Fibonacci wypełnia dp[0..n] od lewej do prawej. Dla i >= 2 zachodzi dp[i] = dp[i-1] + dp[i-2]. Przypadki bazowe to dp[0] = 0 i dp[1] = 1, zapisane bezpośrednio w tablicy. Złożoność czasowa wynosi O(n), a pamięciowa O(n) dla pełnej tabeli. Gdy zauważą Państwo, że dp[i] zależy tylko od dwóch ostatnich wartości, można zmniejszyć zużycie pamięci do O(1) za pomocą dwóch zmiennych — jest to etap optymalizacji pamięci.
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)) # 12586269025Coin Change od dołu
W przypadku coin change tabela DP to dp[0..amount], gdzie dp[i] oznacza minimalną liczbę monet potrzebnych do uzyskania kwoty i. Należy zainicjalizować dp[0] = 0 (zero monet dla kwoty zero), a dp[1..amount] = infinity. Dla każdej kwoty i od 1 do celu należy wypróbować każdą monetę: jeśli i >= coin, wtedy dp[i] = min(dp[i], 1 + dp[i - coin]). Wynikiem jest dp[amount] lub -1, jeśli nadal ma wartość 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)) # 20Kolejność wypełniania: kluczowa obserwacja
Kolejność wypełniania jest sednem DP od dołu. Dla dowolnego stanu dp[i] wszystkie stany, od których on zależy, muszą zostać obliczone wcześniej. W przypadku jednowymiarowego DP, gdy dp[i] zależy od dp[i-1] i dp[i-2], tabelę należy wypełniać od lewej do prawej. W przypadku dwuwymiarowego DP, gdy dp[i][j] zależy od dp[i-1][j] i dp[i][j-1], tabelę należy wypełniać wierszami (z góry na dół, od lewej do prawej). Przed rozpoczęciem implementacji należy zawsze narysować strzałki zależności, aby potwierdzić kolejność wypełniania.
# 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')LCS od dołu: tabela 2D
Tabela DP od dołu dla najdłuższego wspólnego podciągu ma rozmiar (m+1) × (n+1), gdzie dp[i][j] oznacza LCS dla s1[:i] i s2[:j]. Przypadki bazowe: dp[0][j] = dp[i][0] = 0 (pusty łańcuch ma LCS o długości 0 z dowolnym łańcuchem). Tabelę należy wypełniać wierszami: jeśli s1[i-1] == s2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; w przeciwnym razie dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Wynikiem jest 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'Optymalizacja pamięci: tablica krocząca
Wiele dwuwymiarowych tabel DP można zredukować do jednej tablicy (lub dwóch wierszy), obserwując, że dp[i][j] zależy tylko od bieżącego i poprzedniego wiersza. Należy zachować dwie tablice: prev i curr, albo aktualizować pojedynczą tablicę we właściwej kolejności. W przypadku LCS dp[i][j] zależy od dp[i-1][j], dp[i][j-1] i dp[i-1][j-1] — wystarczy zachować tylko poprzedni wiersz.
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)House Robber od dołu
Rozwiązanie House Robber od dołu wypełnia dp[0..n-1], gdzie dp[i] oznacza maksymalny zysk z rabowania domów od 0 do i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]), a dla i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Ponieważ dp[i] zależy tylko od dwóch ostatnich wartości, można od razu zoptymalizować pamięć do O(1) za pomocą dwóch zmiennych — jest to typowy wzorzec dla jednowymiarowego DP z zależnościami obejmującymi dwa poprzednie kroki.
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])) # 12Minimalna suma ścieżki w siatce
Minimum Path Sum (LeetCode #64): należy znaleźć ścieżkę od lewego górnego do prawego dolnego rogu, minimalizującą sumę wartości (można poruszać się wyłącznie w prawo lub w dół). DP 2D: dp[i][j] = minimalna suma potrzebna do dotarcia do komórki (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Tabelę należy wypełniać od lewej do prawej i z góry na dół. Przypadek bazowy: dp[0][0] = grid[0][0], pierwszy wiersz wypełnia się, poruszając się wyłącznie w prawo, a pierwszą kolumnę — wyłącznie w dół.
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+1Modyfikowanie tabeli DP w miejscu
Gdy użycie dodatkowej pamięci jest zabronione, czasami można zmodyfikować samą siatkę wejściową i użyć jej jako tabeli DP. W przypadku minimalnej sumy ścieżki należy nadpisać grid[i][j] minimalnym kosztem dotarcia do tej komórki. Wymaga to O(1) dodatkowej pamięci, ale niszczy dane wejściowe — należy zawsze wspomnieć o tym kompromisie osobie przeprowadzającej rozmowę kwalifikacyjną i potwierdzić, że jest on akceptowalny. Jeśli dane wejściowe muszą zostać zachowane, należy użyć podejścia z tablicą kroczącą.
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))) # 7Porównanie podejść top-down i bottom-up w problemie wydawania reszty
Oba podejścia znajdują optymalne rozwiązanie problemu wydawania reszty, ale w praktyce się różnią. Podejście top-down jest łatwiejsze do zapisania i oblicza tylko te podproblemy, które są rzeczywiście osiągalne. Podejście bottom-up oblicza wszystkie kwoty od 0 do wartości docelowej, także te nieosiągalne przy użyciu podanych monet (pozostają one równe nieskończoności). W przypadku rzadkich problemów (z niewielką liczbą osiągalnych stanów) top-down jest wydajniejsze, natomiast w przypadku gęstych problemów bottom-up ma mniejszy narzut.
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)) # 2Unikalne ścieżki: klasyczne DP 2D
Unikalne ścieżki (LeetCode #62) to problem polegający na policzeniu liczby ścieżek z lewego górnego do prawego dolnego rogu siatki m×n, poruszając się wyłącznie w prawo lub w dół. Rekurencja jest prosta: dp[i][j] = dp[i-1][j] + dp[i][j-1] — ścieżki z góry plus ścieżki z lewej. Przypadki bazowe: w całym pierwszym wierszu i pierwszej kolumnie istnieje dokładnie 1 ścieżka (można poruszać się tylko w jednym kierunku). To DP 2D wypełnia się w czasie O(mn), a pamięć można zmniejszyć do O(n), korzystając z jednego wiersza kroczącego.
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)) # 28Szybki test
Proszę sprawdzić swoje rozumienie pojęć Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji omówiono: programowanie dynamiczne bottom-up z tabulacją oraz sposób wyznaczania kolejności wypełniania na podstawie strzałek zależności, optymalizację pamięci z użyciem tablic kroczących (od O(mn) do O(n)) i śledzenia dwóch zmiennych (od O(n) do O(1)), a także implementacje bottom-up problemów Fibonacciego, wydawania reszty, LCS, rabowania domów i minimalnej sumy ścieżki. Następnie rozwiążemy od początku do końca problemy wydawania reszty i schodów z minimalnym kosztem.
Często zadawane pytania
Czy lekcja „DP z dołu do góry z tabulacją” jest bezpłatna?
Tak — pełny tekst „DP z dołu do góry z tabulacją” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „DP z dołu do góry z tabulacją”?
Przekształcą Państwo rozwiązania top-down w iteracyjne tablice DP i zmniejszą zużycie pamięci z O(n) do O(1), gdy potrzebnych jest tylko kilka ostatnich wpisów. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „DP z dołu do góry z tabulacją”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Rozpoznawanie DP: nakładające się podproblemy
- DP z góry na dół z memoizacją
- DP z dołu do góry z tabulacją
- Wydawanie reszty i schody o minimalnym koszcie