Sia DP che greedy necessitano di sottostruttura ottimale. La differenza: greedy richiede inoltre la greedy-choice property (un ottimo locale è globalmente ottimale), mentre DP è necessaria quando devi considerare più scelte e sottoproblemi sovrapposti.
Optimal substructure? -- both need this
+ greedy-choice property holds? -> GREEDY (fast, one pass of choices)
+ must compare many sub-solutions / they overlap? -> DYNAMIC PROGRAMMING
# Greedy FAILS for coins {1,3,4}, amount 6 -> 4+1+1 (3 coins)
# DP finds the true optimum: 3+3 (2 coins)
def min_coins(amount, coins):
INF = float('inf')
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1) # try every coin
return dp[amount]
min_coins(6, [1, 3, 4]) # -> 2
Greedy si impegna in una scelta; DP esplora tutte e mantiene la migliore.
Greedy è solitamente O(n log n); DP scambia più tempo/spazio (spesso O(n·m)) per correttezza.
Usare greedy senza provare la sua proprietà dà risposte sbagliate che superano test piccoli. In caso di dubbio, scegli DP o verifica greedy contro brute force.
Scegliere greedy quando è valido salva un tempo enorme; sceglierlo quando non lo è produce bug silenziosi.
Sapere quale paradigma si adatta — ed essere in grado di provarlo — è una distinzione di livello senior.
Previene sia l'over-engineering con DP che l'under-delivering con una scelta greedy insostenibile.