Se te proporciona monedas de diferentes denominaciones y una cantidad total de dinero. Escribe una función para calcular el número mínimo de monedas necesarias para alcanzar esa centidad. Si no es posible formar esa cantidad con ninguna combinación de monedas, devuelve -1.

**Ejemplo 1:**denominaciones = [1, 2, 5], cantidad = 11devuelve 3 (11 = 5 + 5 + 1)

**Ejemplo 2:**denominaciones = [2], cantidad = 3devuelve -1.

Nota: Puedes asumir que tienes un número infinito de cada tipo de moneda.

Análisis: Este es un problema clásico de programación dinámica. Inicialmente, podría pansarse en utilizar un algoritmo codicioso, pero este enfoque no garantiza siempre el número mínimo de monedas. Por ejemplo, con cantidad = 8 y denominaciones [1, 3, 5, 6], el enfoque codicioso daría como resultado 3 (6 + 1 + 1), mientras que la solución óptima es 2 (5 + 3). El algoritmo codicioso no funciona aquí porque las decisiones locales no aseguran la solución global óptima.

Existen dos enfoques principales para resolver este problema, aunque ambos se basan en el mismo principio subyacente:

1. Programación Dinámica Iterativa: Creamos un array dp donde dp[n] representa el número mínimo de monedas necesarias para alcanzar la cantidad n. Comenzamos con dp[0] = 0 y construimos la solución de forma iterativa. La relación de reucrrencia es: dp[n] = min(dp[n], dp[n - denominacion] + 1) para cada denominación disponible.
2. Programación Dinámica Recursiva con Memoización: Utilizamos una función recursiva que almacena los resultados intermedios para evitar cálculos redundantes. La relación de recurrencia es: count(n, m) = min(count(n, m-1), count(n - denominaciones[m], m)), donde count es la función que busca el número mínimo de monedas, n es la cantidad objetivo y m es el índice actual de la lista de denominaciones.

Código para el enfoque iterativo:

#include <vector>
#include <algorithm>
#include <climits>

class SolucionCambioMonedas {
public:
    int calcularMinimoMonedas(std::vector<int>& denominaciones, int cantidad) {
        if (denominaciones.empty() && cantidad > 0) {
            return -1;
        }
        
        std::vector<int> tablaDinamica(cantidad + 1, INT_MAX);
        tablaDinamica[0] = 0;
        
        for (const int& valorMoneda : denominaciones) {
            for (int montoActual = valorMoneda; montoActual <= cantidad; ++montoActual) {
                if (tablaDinamica[montoActual - valorMoneda] != INT_MAX) {
                    tablaDinamica[montoActual] = std::min(
                        tablaDinamica[montoActual], 
                        tablaDinamica[montoActual - valorMoneda] + 1
                    );
                }
            }
        }
        
        return tablaDinamica[cantidad] == INT_MAX ? -1 : tablaDinamica[cantidad];
    }
};

Enfoque alternativo: Solución recursiva DFS con memoización

Utilizamos un array para registrar los estados previamente calculados.

#include <vector>
#include <algorithm>
#include <climits>

class SolucionCambioMonedasRecursiva {
public:
    int calcularMinimoMonedas(std::vector<int>& denominaciones, int cantidad) {
        if (cantidad < 1) return 0;
        std::vector<int> memo(cantidad, 0);
        return resolverCambio(denominaciones, cantidad, memo);
    }

private:
    int resolverCambio(std::vector<int>& denominaciones, int resto, std::vector<int>& memo) {
        if (resto < 0) return -1;
        if (resto == 0) return 0;
        if (memo[resto - 1] != 0) return memo[resto - 1];
        
        int minimo = INT_MAX;
        for (const int& valorMoneda : denominaciones) {
            int resultado = resolverCambio(denominaciones, resto - valorMoneda, memo);
            if (resultado >= 0 && resultado < minimo) {
                minimo = 1 + resultado;
            }
        }
        
        memo[resto - 1] = (minimo == INT_MAX ? -1 : minimo);
        return memo[resto - 1];
    }
};