Programación Dinámica y Algoritmos Voraces

1. Programación Dinámica (DP): Se usa cuando un problema tiene subproblemas que se repiten.
2. Algoritmos Voraces (Greedy): Se usa cuando siempre tomamos la mejor opción localmente, esperando que sea la mejor globalmente.

✅ Objetivo:

• Entender cuándo usar Programación Dinámica y cuándo usar Greedy.
• Implementar ejemplos en Java, JavaScript, TypeScript y Python.

1. 1. Programación Dinámica (DP) #

La programación dinámica optimiza problemas dividiéndolos en subproblemas más pequeños y almacenando las soluciones para evitar cálculos repetidos.

📌 Ejemplo clásico: Fibonacci con DP
Si calculamos Fibonacci de forma recursiva, recalculamos valores repetidos:

1// Java - O(2ⁿ) - Fibonacci Recursivo sin optimización
2public class Fibonacci {
3    public static int fib(int n) {
4        if (n <= 1) return n;
5        return fib(n - 1) + fib(n - 2);
6    }
7}

✅ Solución: Memorización (Top-Down DP)
Almacenamos los valores ya calculados para evitar repeticiones.

✅ Análisis:

• Sin DP (O(2ⁿ)): Muy lento debido a cálculos repetidos.
• Con DP (O(n)): Mucho más rápido porque evitamos recalcular valores.

2. 2. Tabulación (Bottom-Up DP) #

Otra forma de Programación Dinámica es usar una tabla iterativa en lugar de recursión.

📌 Ejemplo: Fibonacci con Tabulación

1// Java - O(n) - Fibonacci con Tabulación
2public class FibonacciTabulation {
3    public static int fib(int n) {
4        if (n <= 1) return n;
5        int[] dp = new int[n + 1];
6        dp[0] = 0;
7        dp[1] = 1;
8        for (int i = 2; i <= n; i++) {
9            dp[i] = dp[i - 1] + dp[i - 2];
10        }
11        return dp[n];
12    }
13}

✅ Diferencias entre DP con Memorización y Tabulación

📌 Conclusión:
Ambos métodos reducen la complejidad de Fibonacci de O(2ⁿ) a O(n).

3. 3. Algoritmos Voraces (Greedy) #

Los algoritmos voraces toman la mejor decisión en cada paso sin preocuparse por el futuro.

✅ Cuándo usar Greedy:

1. Cuando una decisión óptima local conduce a una solución global óptima.
2. Cuando podemos ordenar los datos y siempre elegir la mejor opción.

📌 Ejemplo: Problema del Cambio de Monedas Supongamos que queremos dar 27€ usando la menor cantidad de monedas {10€, 5€, 1€}.

🔹 Estrategia voraz:

• Primero usamos la moneda más grande posible.
• Luego seguimos con las más pequeñas.

✅ Ejemplo con amount = 27 y coins = [10, 5, 1]:
Salida: [10, 10, 5, 1, 1]
El algoritmo elige la moneda más grande primero y luego las más pequeñas.

4. 4. Comparación entre Programación Dinámica y Algoritmos Voraces #