Programa Python para Cambio de Moneda – Part 1

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. 

# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):
    # We need n+1 rows as the table is constructed
    # in bottom up manner using the base case 0 value
    # case (n = 0)
    table = [[0 for x in range(m)] for x in range(n+1)]
 
    # Fill the entries for 0 value case (n = 0)
    for i in range(m):
        table[0][i] = 1
 
    # Fill rest of the table entries in bottom up manner
    for i in range(1, n+1):
        for j in range(m):
 
            # Count of solutions including S[j]
            x = table[i - S[j]][j] if i-S[j] >= 0 else 0
 
            # Count of solutions excluding S[j]
            y = table[i][j-1] if j >= 1 else 0
 
            # total count
            table[i][j] = x + y
 
    return table[n][m-1]
 
# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 4
print(count(arr, m, n))
 
# This code is contributed by Bhavya Jain

# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):
 
    # 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)
    # Initialize all table values as 0
    table = [0 for k in range(n+1)]
 
    # 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 i in range(0,m):
        for j in range(S[i],n+1):
            table[j] += table[j-S[i]]
 
    return table[n]
 
# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 4
x = count(arr, m, n)
print (x)
 
# This code is contributed by Afzal Ansari

Análisis de Complejidad:

Para ambas soluciones, la complejidad de tiempo y espacio es la misma:

Complejidad de tiempo: O(n*m)

Complejidad espacial: O(n)

Aunque la primera solución puede ser un poco lenta ya que tiene múltiples bucles.

Consulte el artículo completo sobre programación dinámica | ¡ Establezca 7 (Cambio de moneda) para más detalles!