Riconoscere la DP: sottoproblemi sovrapposti
Individui quando la ricorsione brute-force risolve nuovamente lo stesso sottoproblema, disegni l'albero ricorsivo di Fibonacci e osservi la crescita esponenziale
Riconoscere la DP: sottoproblemi sovrapposti è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è la programmazione dinamica
La programmazione dinamica (DP) risolve problemi complessi suddividendoli in sottoproblemi più semplici e sovrapposti, risolvendo ogni sottoproblema una sola volta e memorizzando il risultato per evitare calcoli ridondanti. La DP si applica quando un problema presenta due caratteristiche: sottoproblemi sovrapposti (lo stesso sottoproblema viene risolto più volte in una ricorsione ingenua) e sottostruttura ottimale (la soluzione ottimale può essere costruita a partire dalle soluzioni ottimali dei sottoproblemi). In assenza di entrambe, la DP non è utile.
# Two ingredients of DP:
# 1. Overlapping sub-problems:
# fib(5) -> fib(4) + fib(3)
# fib(4) -> fib(3) + fib(2) <- fib(3) computed twice!
# Without caching: O(2^n) calls for Fibonacci
# 2. Optimal substructure:
# Shortest path from A to C through B:
# shortest(A,C) = shortest(A,B) + shortest(B,C)
# The sub-path A->B must itself be the shortest
# Contrast with greedy: greedy makes one locally optimal
# choice; DP tries all choices and picks the best.
print('DP = overlapping sub-problems + optimal substructure')Fibonacci: il punto di partenza classico per la DP
La successione di Fibonacci (fib(n) = fib(n-1) + fib(n-2)) è l'esempio canonico di sottoproblemi sovrapposti. La ricorsione ingenua ha complessità temporale esponenziale O(2^n), perché ricalcola ripetutamente gli stessi valori. L'albero della ricorsione per fib(6) mostra che fib(3) viene calcolato 3 volte, fib(2) 5 volte e così via. Questa crescita esponenziale è esattamente ciò che la DP elimina memorizzando i risultati già calcolati.
import time
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
# Count the calls:
call_count = [0]
def fib_count(n):
call_count[0] += 1
if n <= 1: return n
return fib_count(n-1) + fib_count(n-2)
fib_count(10)
print(f'Calls for fib(10): {call_count[0]}') # 177 calls for n=10!
call_count[0] = 0
fib_count(20)
print(f'Calls for fib(20): {call_count[0]}') # 21891 calls
# n=30 -> ~2.7 million calls: exponential growthVisualizzazione dell'albero della ricorsione
Disegnare l'albero della ricorsione per fib(5) rivela lo spreco: ogni nodo genera due figli e sottoalberi identici compaiono ripetutamente. Il numero totale di nodi nell'albero è O(2^n). Quando si osserva questo schema, con chiamate di funzione identiche e gli stessi argomenti ripetute nell'albero, significa che la DP può essere utile memorizzando i risultati nella cache. Questa capacità di visualizzazione è fondamentale: se si riescono a individuare i sottoalberi ripetuti, si sa che la DP è applicabile.
# fib(5) recursion tree (simplified):
# fib(5)
# / \
# fib(4) fib(3)
# / \ / \
# fib(3) fib(2) fib(2) fib(1)
# / \ \
# fib(2) fib(1) fib(1)
# / \
# fib(1) fib(0)
# fib(3) appears TWICE
# fib(2) appears THREE TIMES
# Each redundant call wastes exponential time
# Key insight: fib(n) only has O(n) DISTINCT sub-problems
# (fib(0), fib(1), ..., fib(n))
# DP computes each ONCE -> O(n) total
print('Distinct sub-problems: O(n) but naive calls: O(2^n)')Individuazione dei sottoproblemi sovrapposti
Per riconoscere i sottoproblemi sovrapposti, si scriva prima la ricorsione a forza bruta, quindi ci si chieda: 'ci sono più chiamate ricorsive con gli STESSI argomenti?'. Se la risposta è sì, la DP può essere utile. Alcuni segnali comuni nelle descrizioni dei problemi sono: 'numero minimo/massimo di X', 'in quanti modi si può ottenere Y' e 'è possibile ottenere Z?'. Queste formulazioni indicano quasi sempre un problema con sottostruttura ottimale, in cui la risposta nella posizione i dipende dalle risposte nelle posizioni precedenti.
# DP signal phrases in problem statements:
# 'minimum number of coins to make amount X'
# 'maximum profit from stock trades'
# 'number of ways to climb n stairs'
# 'can you reach the last index?'
# 'longest common subsequence'
# 'edit distance between two strings'
# All have this shape:
# solve(input) = f(solve(smaller_input_1), solve(smaller_input_2), ...)
# And multiple branches end up calling solve with the same argument.
# If the recursion tree has repeated nodes: DP
# If subproblems are all independent: divide-and-conquer (no DP needed)
print('Repeated arguments in recursion tree -> DP')Spiegazione della sottostruttura ottimale
La sottostruttura ottimale significa che la soluzione ottimale del problema può essere costruita a partire dalle soluzioni ottimali dei sottoproblemi. Per esempio, il cammino minimo da A a C passando per B è ottimale se e solo se i sottocammini A→B e B→C sono entrambi ottimali. Se questa proprietà vale, è possibile costruire l'ottimo globale dal basso verso l'alto a partire dagli ottimi locali. I problemi privi di sottostruttura ottimale, come il cammino più lungo in un grafo generale con cicli, non possono essere risolti con la DP.
# Optimal substructure examples:
# SHORTEST PATH: shortest(A,C) = min over all B: shortest(A,B) + w(B,C)
# -> Sub-paths must be optimal: YES, has optimal substructure
# LONGEST PATH (no cycles, DAG): can also use DP
# -> Longer path through node B means sub-path A->B must be longest
# LONGEST PATH (with cycles): NO optimal substructure
# -> Best path from A to C might reuse nodes: sub-problems not independent
# COIN CHANGE: min coins for amount n = 1 + min(min coins for n-coin_i)
# -> YES: optimal for n-coin_i is needed for optimal n
print('Optimal substructure: build global optimum from local optima')Climbing Stairs: la prima DP
Climbing Stairs (LeetCode #70): in quanti modi distinti si possono salire n gradini facendo 1 o 2 passi alla volta? Si definisca dp[i] come il numero di modi per raggiungere il gradino i. È possibile arrivare al gradino i dal gradino i-1, con un passo, oppure dal gradino i-2, con due passi; quindi dp[i] = dp[i-1] + dp[i-2]. È Fibonacci! Casi base: dp[1] = 1, dp[2] = 2. Riconoscere che 'salire le scale' si riduce a Fibonacci è un'intuizione classica nei colloqui tecnici.
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1 # 1 way to reach step 1
dp[2] = 2 # 2 ways to reach step 2: (1+1) or (2)
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2] # come from i-1 or i-2
return dp[n]
for n in range(1, 8):
print(f'climb_stairs({n}) = {climb_stairs(n)}')
# 1, 2, 3, 5, 8, 13, 21 -- Fibonacci sequence!Framework DP: definire lo stato, formulare la ricorrenza, stabilire l'ordine
Un framework DP affidabile in 3 passaggi: 1. Definisca lo stato — che cosa rappresenta dp[i] (o dp[i][j])? Lo scriva in inglese. 2. Scriva la ricorrenza — esprima dp[i] in termini di sottoproblemi più piccoli. Includa tutti i casi. 3. Stabilisca l'ordine di riempimento — si assicuri che dp[i-1] (e le altre dipendenze) siano calcolati prima di dp[i]. I casi base inizializzano il confine. Questo framework trasforma l'intuizione sfumata della DP in un piano concreto di implementazione.
# Framework applied to climbing stairs:
# Step 1 - Define state:
# dp[i] = number of distinct ways to reach step i
# Step 2 - Recurrence:
# dp[i] = dp[i-1] + dp[i-2] (come from step i-1 or i-2)
# Step 3 - Fill order:
# Compute dp[1], dp[2], dp[3], ..., dp[n] in order
# Because dp[i] depends on dp[i-1] and dp[i-2] (smaller)
# Base cases: dp[1]=1, dp[2]=2
# Framework applied to coin change:
# Step 1: dp[amount] = minimum coins to make that amount
# Step 2: dp[i] = 1 + min(dp[i-coin] for coin in coins if i >= coin)
# Step 3: Fill i from 1 to amount
# Base: dp[0] = 0 (zero coins for zero amount)
print('DP framework: define state -> recurrence -> fill order')Quando NON usare la DP
La DP non è sempre la risposta. Usi greedy quando una singola scelta ottimale a livello locale porta sempre alla soluzione globalmente ottimale (activity selection, jump game I). Usi divide et impera quando i sottoproblemi non si sovrappongono (merge sort, ricerca binaria). Usi BFS quando il problema consiste nel trovare il percorso più breve in un grafo non pesato. La DP è corretta, ma spesso è eccessiva quando esiste un approccio greedy o più semplice. Nei colloqui, spieghi perché ha scelto la DP invece delle alternative.
# DP vs alternatives:
# Problem: can you jump to the end of the array?
# Greedy: track max reachable index -> O(n) O(1) BETTER than DP
# Problem: shortest path unweighted graph?
# BFS: O(V+E) BETTER than DP on general graph
# Problem: sort an array?
# Comparison sort: O(n log n), no DP needed
# DP IS the right choice when:
# - Greedy fails (choices interact)
# - Need to count/enumerate all possibilities
# - Problem has 'how many ways' or 'minimum/maximum' flavor
# - Recursion tree clearly shows overlapping sub-problems
print('Ask: does greedy fail? If yes, consider DP.')Contare i sottoproblemi distinti
Il numero dei sottoproblemi distinti determina la complessità temporale e spaziale della DP. Per una DP 1D su un input di dimensione n, ci sono O(n) sottoproblemi. Per una DP 2D su due input di dimensioni m e n, ci sono O(mn) sottoproblemi. Se ogni sottoproblema viene risolto in O(k) tempo (con k scelte a ogni passaggio), il tempo totale è O(n*k) o O(mn*k). Conti sempre prima i sottoproblemi distinti: in questo modo determina la complessità temporale della DP prima ancora di implementarla.
# Sub-problem count examples:
# Problem | Sub-problems | Each costs | Total
# Fibonacci | O(n) | O(1) | O(n)
# Coin change | O(amount) | O(coins) | O(amount * coins)
# LCS (m,n chars) | O(m*n) | O(1) | O(m*n)
# Edit distance | O(m*n) | O(1) | O(m*n)
# 0/1 Knapsack | O(n*W) | O(1) | O(n*W)
# Matrix chain | O(n^2) | O(n) | O(n^3)
# Rule: DP time = (# distinct sub-problems) * (time per sub-problem)
print('Time = subproblems * work-per-subproblem')House Robber: scelte sovrapposte
House Robber (LeetCode #198) chiede qual è l'importo massimo che si può rubare da una fila di case senza derubare due case adiacenti. A ogni casa, scelga: derubarla (aggiungere il suo valore e saltare la precedente) oppure saltarla (prendere il risultato migliore della precedente). dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Questo schema di scelta a ogni passaggio è la ricorrenza DP 1D più semplice e compare in decine di problemi da colloquio.
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
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], # skip house i
dp[i-2] + nums[i]) # rob house i
return dp[-1]
print(rob([1, 2, 3, 1])) # 4: rob house 0 and 2 (1+3)
print(rob([2, 7, 9, 3, 1]))# 12: rob house 0, 2, 4 (2+9+1)
print(rob([2, 1, 1, 2])) # 4: rob house 0 and 3Controllo di coerenza: forza bruta e DP
Verifichi sempre la DP confrontandola con una soluzione a forza bruta su input piccoli. La forza bruta è il riferimento corretto. Quando la DP coincide con la forza bruta in tutti i casi di test, sa che la ricorrenza è corretta. Solo a quel punto ottimizzi lo spazio. Questo approccio basato sui test — forza bruta → DP top-down → DP bottom-up → DP con spazio ottimizzato — è il metodo professionale per sviluppare e verificare soluzioni DP durante un colloquio.
# Brute-force for house robber (exponential)
def rob_brute(nums, i=0):
if i >= len(nums):
return 0
# Option 1: rob house i
rob_it = nums[i] + rob_brute(nums, i + 2)
# Option 2: skip house i
skip_it = rob_brute(nums, i + 1)
return max(rob_it, skip_it)
# Verify on small inputs:
test_cases = [[1,2,3,1], [2,7,9,3,1], [2,1,1,2]]
for tc in test_cases:
bf = rob_brute(tc)
dp = rob(tc)
print(f'{tc}: brute={bf}, dp={dp}, match={bf==dp}')Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso: i due ingredienti della DP (sottoproblemi sovrapposti e struttura ottimale), come visualizzare l'albero della ricorsione per individuare le chiamate ripetute, il framework DP in tre passaggi (definire lo stato, la ricorrenza e l'ordine di riempimento) e i primi esempi, tra cui Fibonacci, climbing stairs e House Robber. Nel prossimo passaggio implementerà la DP top-down con la memoizzazione.
Domande Frequenti
La lezione «Riconoscere la DP: sottoproblemi sovrapposti» è gratuita?
Sì — il testo completo di «Riconoscere la DP: sottoproblemi sovrapposti» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Riconoscere la DP: sottoproblemi sovrapposti»?
Individui quando la ricorsione brute-force risolve nuovamente lo stesso sottoproblema, disegni l'albero ricorsivo di Fibonacci e osservi la crescita esponenziale Eserciti Coding 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding 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 1 di 4.
Quanto tempo richiede la lezione «Riconoscere la DP: sottoproblemi sovrapposti»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding 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