DP bottom-up con tabulation
Converta le soluzioni top-down in tabelle DP iterative e riduca lo spazio da O(n) a O(1) quando servono soltanto le ultime voci
DP bottom-up con tabulation è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
DP bottom-up: approccio della tabulazione
La DP bottom-up (tabulazione) riempie una tabella con le risposte ai sottoproblemi, partendo dai più piccoli e arrivando alla soluzione. Invece di scendere ricorsivamente e memorizzare i risultati durante la risalita, calcola tutto iterativamente dal basso verso l'alto. La tabella è in genere un array 1D o 2D, in cui ogni cella viene calcolata a partire da celle già riempite. In questo modo si elimina completamente la ricorsione: niente stack delle chiamate, nessun limite di ricorsione e una migliore località della cache.
# 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 bottom-up
La versione bottom-up di Fibonacci riempie dp[0..n] da sinistra a destra. dp[i] = dp[i-1] + dp[i-2] per i >= 2. I casi base sono dp[0] = 0 e dp[1] = 1, memorizzati direttamente nell'array. Il tempo è O(n) e lo spazio è O(n) per la tabella completa. Una volta osservato che dp[i] dipende solo dagli ultimi due valori, può ridurre lo spazio a O(1) usando due variabili: questo è il passaggio di ottimizzazione dello spazio.
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 bottom-up
Per coin change, la tabella bottom-up è dp[0..amount], dove dp[i] = numero minimo di monete per ottenere l'importo i. Inizializzi dp[0] = 0 (zero monete per un importo nullo) e dp[1..amount] = infinito. Per ogni importo i da 1 al target, provi ogni moneta: se i >= coin, allora dp[i] = min(dp[i], 1 + dp[i - coin]). La risposta è dp[amount], oppure -1 se il valore è ancora infinito.
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)) # 20Ordine di riempimento: l'intuizione fondamentale
L'ordine di riempimento è il cuore della DP bottom-up. Per qualsiasi stato dp[i], tutti gli stati da cui dipende devono essere calcolati prima. Per una DP 1D in cui dp[i] dipende da dp[i-1] e dp[i-2], riempia da sinistra a destra. Per una DP 2D in cui dp[i][j] dipende da dp[i-1][j] e dp[i][j-1], riempia riga per riga (dall'alto verso il basso, da sinistra a destra). Disegni sempre le frecce delle dipendenze prima di scrivere il codice, per confermare l'ordine di riempimento.
# 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 bottom-up: tabella 2D
La tabella bottom-up della sottosequenza comune più lunga ha dimensioni (m+1) × (n+1), dove dp[i][j] = LCS di s1[:i] e s2[:j]. Casi base: dp[0][j] = dp[i][0] = 0 (la stringa vuota ha LCS 0 con qualsiasi altra stringa). Riempia la tabella riga per riga: se s1[i-1] == s2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; altrimenti dp[i][j] = max(dp[i-1][j], dp[i][j-1]). La risposta è 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'Ottimizzazione dello spazio: rolling array
Molte tabelle DP 2D possono essere ridotte a 1D (o a 2 righe) osservando che dp[i][j] dipende solo dalla riga corrente e da quella precedente. Mantenga due array: prev e curr, oppure aggiorni un singolo array nell'ordine corretto. Per LCS, dp[i][j] dipende da dp[i-1][j], dp[i][j-1] e dp[i-1][j-1]: è sufficiente mantenere solo la riga precedente.
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 bottom-up
Nella versione bottom-up di House Robber si riempie dp[0..n-1], dove dp[i] = profitto massimo derubando le case da 0 a i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) e, per i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Poiché dp[i] dipende solo dagli ultimi due valori, si può ottimizzare immediatamente lo spazio a O(1) usando due variabili: uno schema comune nella DP 1D con dipendenze su due passaggi.
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])) # 12Somma minima del percorso in una griglia
Minimum Path Sum (LeetCode #64): trovi un percorso dall'angolo in alto a sinistra a quello in basso a destra che minimizzi la somma dei valori (è possibile muoversi solo a destra o verso il basso). DP 2D: dp[i][j] = somma minima per raggiungere la cella (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Riempia la tabella da sinistra a destra e dall'alto verso il basso. Caso base: dp[0][0] = grid[0][0]; la prima riga si riempie solo verso destra e la prima colonna solo verso il basso.
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+1Modificare la tabella DP sul posto
Quando non è consentito usare spazio aggiuntivo, a volte è possibile modificare direttamente la griglia di input e usarla come tabella DP. Per la somma minima del percorso, sovrascriva grid[i][j] con il costo minimo per raggiungere quella cella. In questo modo usa O(1) di spazio aggiuntivo, ma distrugge l'input: comunichi sempre questo compromesso all'intervistatore e confermi che sia accettabile. Se è necessario preservare l'input, usi invece l'approccio dell'array rolling.
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))) # 7Confronto tra gli approcci top-down e bottom-up al problema del resto
Entrambi gli approcci risolvono il problema del resto in modo ottimale, ma nella pratica presentano differenze. L'approccio top-down è più semplice da scrivere e calcola solo i sottoproblemi effettivamente raggiungibili. L'approccio bottom-up calcola tutti gli importi da 0 al valore obiettivo, anche quelli irraggiungibili con le monete disponibili, che rimangono quindi a infinito. Per problemi sparsi, con pochi stati raggiungibili, il top-down è più efficiente; per problemi densi, il bottom-up ha un overhead inferiore.
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)) # 2Percorsi unici: DP 2D classica
Percorsi unici (LeetCode #62) calcola il numero di percorsi dall'angolo in alto a sinistra all'angolo in basso a destra di una griglia m×n, muovendosi solo verso destra o verso il basso. La ricorrenza è immediata: dp[i][j] = dp[i-1][j] + dp[i][j-1] — i percorsi dall'alto più quelli da sinistra. Casi base: l'intera prima riga e l'intera prima colonna hanno esattamente 1 percorso ciascuna, perché c'è una sola direzione possibile. Questa DP 2D richiede O(mn) tempo e può essere ridotta a O(n) spazio usando una riga a scorrimento.
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)) # 28Controllo rapido
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: la DP bottom-up con tabulazione e come determinare l'ordine di riempimento a partire dalle frecce delle dipendenze, l'ottimizzazione dello spazio usando array a scorrimento (da O(mn) a O(n)) e il mantenimento di due variabili (da O(n) a O(1)), oltre alle implementazioni bottom-up di Fibonacci, problema del resto, LCS, ladro di case e somma minima del percorso. Ora risolveremo dall'inizio alla fine i problemi del resto e della scala a costo minimo.
Domande Frequenti
La lezione «DP bottom-up con tabulation» è gratuita?
Sì — il testo completo di «DP bottom-up con tabulation» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «DP bottom-up con tabulation»?
Converta le soluzioni top-down in tabelle DP iterative e riduca lo spazio da O(n) a O(1) quando servono soltanto le ultime voci Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «DP bottom-up con tabulation»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Riconoscere la DP: sottoproblemi sovrapposti
- DP top-down con memoisation
- DP bottom-up con tabulation
- Coin change e scala a costo minimo