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. 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.

1import java.util.HashMap;
2import java.util.Map;
3
4public class FibonacciDP {
5    private static Map<Integer, Integer> memo = new HashMap<>();
6    
7    public static int fib(int n) {
8        if (n <= 1) return n;
9        if (memo.containsKey(n)) return memo.get(n);
10        int result = fib(n - 1) + fib(n - 2);
11        memo.put(n, result);
12        return result;
13    }
14}

✅ 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. 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. 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.

1import java.util.*;
2
3public class CoinChangeGreedy {
4    public static List<Integer> change(int amount, int[] coins) {
5        Arrays.sort(coins); // Ordenamos las monedas
6        List<Integer> result = new ArrayList<>();
7        for (int i = coins.length - 1; i >= 0; i--) {
8            while (amount >= coins[i]) {
9                amount -= coins[i];
10                result.add(coins[i]);
11            }
12        }
13        return result;
14    }
15}

✅ 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. Comparación entre Programación Dinámica y Algoritmos Voraces

📌 Conclusión:

• Si un problema tiene subproblemas repetidos → Usar Programación Dinámica.
• Si siempre podemos tomar la mejor decisión en cada paso → Usar Greedy.