Fundamentos de programación dinámica
Para subproblemas TRASLAPADOS: calcula cada uno una vez, recuérdalo.
DP = recursión + memoria.
El problema con la recursión ingenua
- Mínimo de monedas para a = 1 + min sobre monedas de (mínimo para a−c)
- Los mismos submontos se repiten entre ramas → recálculo exponencial
- Fibonacci: fib(5) calcula fib(2) tres veces → O(φⁿ)
- Los subproblemas se TRASLAPAN, y la recursión ingenua es ciega a eso
Dos estilos, la misma tabla
- Top-down (memoizar): la recurrencia + un cache;
@lru_cache lo hace gratis
- Bottom-up (tabular): llena dp[0..n] desde el más chico, sin recursión
- Ambos: cada subproblema calculado UNA VEZ → O(amount × #coins)
- Necesita subestructura óptima + subproblemas traslapados
Mira la tabla llenarse
dp[a] = 1 + min(dp[a−1], dp[a−3], dp[a−4]). Cada celda consultada ya está lista.
dp[6] = 2 (3+3) — donde el 4+1+1 = 3 de greedy se equivocó.
Exponencial → polinomial
Monto 20: ingenua 38,000 llamadas, DP 60 → 640× menos. La DP cambia la CLASE de complejidad.
Para llevar
La parte difícil es definir el ESTADO + la recurrencia; la memoización es mecánica.
Resuelve lo que greedy no puede (greedy se equivoca 13% aquí) considerando todas las opciones.
Sigue: knapsack — la DP que greedy demostrablemente no puede resolver.