Dado un valor N, si queremos dar cambio por N centavos, y tenemos un suministro infinito de cada una de las monedas valoradas en S = { S1, S2, .. , Sm}, ¿de cuántas formas podemos hacer el cambio? El orden de las monedas no importa.
Por ejemplo, para N = 4 y S = {1,2,3}, hay cuatro soluciones: {1,1,1,1},{1,1,2},{2,2},{1, 3}. Entonces, la salida debería ser 4. Para N = 10 y S = {2, 5, 3, 6}, hay cinco soluciones: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} y {5,5}. Entonces la salida debería ser 5.
Java
/* Dynamic Programming Java implementation of Coin
Change problem */
import java.util.Arrays;
class CoinChange
{
static long countWays(int S[], int m, int n)
{
// Time complexity of this function: O(mn)
// table[i] will be storing the number of solutions
// for value i. We need n+1 rows as the table is
// constructed in bottom up manner using the base
// case (n = 0)
long[] table = new long[n+1];
// Initialize all table values as 0
Arrays.fill(table, 0); //O(n)
// Base case (If given value is 0)
table[0] = 1;
// Pick all coins one by one and update the table[]
// values after the index greater than or equal to
// the value of the picked coin
for (int i=0; i<m; i++)
for (int j=S[i]; j<=n; j++)
table[j] += table[j-S[i]];
return table[n];
}
// Driver Function to test above function
public static void main(String args[])
{
int arr[] = {1, 2, 3};
int m = arr.length;
int n = 4;
System.out.println(countWays(arr, m, n));
}
}
// This code is contributed by Pankaj Kumar
¿Escribir código en un comentario? Utilice ide.geeksforgeeks.org , genere un enlace y compártalo aquí.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA