LeetCode – Cambio de moneda (Java)

Dado un conjunto de monedas y una cantidad total de dinero. Escribe un método para calcular la menor cantidad de monedas para completar la cantidad dada. Si la cantidad no se puede compensar con ninguna combinación de las monedas dadas, devuelve -1.

Por ejemplo:
Dado [2, 5, 10] y cantidad = 6, el método debería devolver -1.
Dado [1, 2, 5] y cantidad = 7, el método debería devolver 2.

Solución Java 1 – Programación dinámica (mirando hacia atrás)

La solución es usar una matriz 2-D para DP. Si miramos el valor de la columna de cantidad anterior que se usa en la columna de cantidad posterior, la columna posterior solo se preocupa por el valor mínimo de la columna anterior. Por lo tanto, podemos usar una matriz 1-D en lugar de la matriz 2-D.

Dada una cantidad de 6 y monedas [1,2,5], podemos mirar hacia atrás en la matriz dp.

Let dp[i] to be the minimum number of coins required to get the amount i. 
dp[i] = 1, if i==coin
otherwise, dp[i]=min(dp[i-coin]+1, dp[i]) if dp[i-coin] is reachable. 
We initially set dp[i] to be MAX_VALUE. 

public int coinChange(int[] coins, int amount) {
    if(amount==0){
        return 0;
    }
 
    int[] dp = new int[amount+1];
 
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0]=0;
 
    for(int i=1; i<=amount; i++){
        for(int coin: coins){
            if(i==coin){
                dp[i]=1;
            }else if(i>coin){
                if(dp[i-coin]==Integer.MAX_VALUE){
                    continue;
                }
                dp[i]=Math.min(dp[i-coin]+1, dp[i]);
            }
        }
    }
 
    if(dp[amount]==Integer.MAX_VALUE){
        return -1;
    }
 
    return dp[amount];
}

La complejidad del tiempo es O (cantidad * num_of_coins) y la complejidad del espacio es O (cantidad).

Solución Java 2 – Programación dinámica (mirando hacia el futuro)

Let dp[i] to be the minimum number of coins required to get the amount i. 
dp[i+coin] = min(dp[i+coin], dp[i]+1) if dp[i] is reachable. 
dp[i+coin] = dp[i+coin] is dp[i] is not reachable. 
We initially set dp[i] to be MAX_VALUE. 

Aquí está el código de Java:

public int coinChange(int[] coins, int amount) {
    if(amount==0){
        return 0;
    }
 
    int[] dp = new int[amount+1];
 
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0]=0;
 
    for(int i=0; i<=amount; i++){
        if(dp[i]==Integer.MAX_VALUE){
            continue;
        }
 
        for(int coin: coins){
            if(i<=amount-coin){ //handle case when coin is Integer.MAX_VALUE
                dp[i+coin] = Math.min(dp[i]+1, dp[i+coin]);
            }
        }
    }
 
    if(dp[amount]==Integer.MAX_VALUE){
        return -1;
    }
 
    return dp[amount];
}

El tiempo y el espacio son los mismos que en la Solución 1.

Solución Java 3 – Breath First Search (BFS)

Los problemas de programación dinámica a menudo se pueden resolver utilizando BFS.

Podemos ver este problema como ir a una posición de destino con pasos que están permitidos en la matriz. coins. Mantenemos dos colas: una de la cantidad hasta ahora y la otra para los pasos mínimos. El tiempo es demasiado debido al método contains, tome n y el tiempo total es O (n ^ 3).

public int coinChange(int[] coins, int amount) {
	if (amount == 0)
		return 0;
 
	LinkedList<Integer> amountQueue = new LinkedList<Integer>();
	LinkedList<Integer> stepQueue = new LinkedList<Integer>();
 
	// to get 0, 0 step is required
	amountQueue.offer(0);
	stepQueue.offer(0);
 
	while (amountQueue.size() > 0) {
		int temp = amountQueue.poll();
		int step = stepQueue.poll();
 
		if (temp == amount)
			return step;
 
		for (int coin : coins) {
			if (temp > amount) {
				continue;
			} else {
				if (!amountQueue.contains(temp + coin)) {
					amountQueue.offer(temp + coin);
					stepQueue.offer(step + 1);
				}
			}
		}
	}
 
	return -1;
}