# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Minimum number of Coins for Change
#
# ### Using Dynamic Programming
#
# If solution exists -> Dynamic Programming will find it and it will be able to find OPTIMAL Solution, compared to Recusion and Greedy.

# +
coins = [2, 3, 5, 10]
w = 15

coins_mat = []
# -

A = [[None for i in range(16)] for j in coins]
A[0] = [1 if j % coins[0] == 0 else 0 for j in range(len(A[0]))]
A[0]

A[0][15]


# +
def get_num_of_coins(coins, w):
    A = [[None for i in range(w + 1)] for j in coins]
    A[0] = [1 if j % coins[0] == 0 else 0 for j in range(len(A[0]))]
    num_coins = len(A)
    for i in range(1, num_coins):
        for j in range(w+1):
            if coins[i] > j:
                A[i][j] = A[i - 1][j]
            else:
                A[i][j] = A[i - 1][j] + A[i][j - coins[i]]         
    print(A)
    return A[len(A) - 1][len(A[0]) - 1]

def exclude_include_sum(coin, sum):
    
    

# +
coins = [2, 3, 5, 10]
w = 15
min_coins = get_num_of_coins(coins, w)
print(min_coins)
    
coins = [1, 5, 10]
w = 7
min_coins = get_num_of_coins(coins, w)
print(min_coins)

coins = [2, 3, 5]
w = 6
min_coins = get_num_of_coins(coins, w)
print(min_coins)
# -





StarcoderdataJupyterScriptsDedupFiltered