Tanto DP como voraz necesitan subestructura óptima. La diferencia: voraz también requiere la propiedad de elección voraz (un óptimo local es globalmente óptimo), mientras que DP es necesario cuando debes considerar múltiples opciones y subproblemas superpuestos.
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
Voraz se compromete con una opción; DP explora todas y mantiene la mejor.
Voraz es generalmente O(n log n); DP intercambia más tiempo/espacio (a menudo O(n·m)) por corrección.
Usar voraz sin probar su propiedad da respuestas incorrectas que pasan pruebas pequeñas. En caso de duda, recurre a DP o verifica voraz contra fuerza bruta.
Elegir voraz cuando es válido ahorra tiempo enorme; elegirlo cuando no es válido produce errores silenciosos.
Saber qué paradigma se ajusta — y poder probarlo — es una distinción de nivel senior.
Previene tanto la sobre-ingeniería con DP como la entrega insuficiente con una opción voraz insegura.