PYTHON 3

Follow Directions

Problem

Given a set of coin values, we want to find the least number of coins necessary for making a given change where we have an infinite number of each coin value.

For example, if we have pennies, nickels and quarters (i.e. [1, 5, 25]), and we are asking what's the minimum number of coins needed to make a change of 62 cents, the answer is 6: two quarters, two nickels, and two pennies.

Complete the function minCoins() to return the number of minimum coins necessary to make the required change, where the set of possible coin values are given by the choices array.

Your solution must use Dynamic Programming with memoization :)

Hint

Since we want to use Dynamic Programming for this problem, we know that it has the optimal sub-structure property. In this case, the minCoins() at each step is the minimum of all possible choices we can make for the given change (i.e. all possible sub-problems). In other words, when we start with our change as 62, we have 3 choices for the first coin:

pick a penny, we will now have to make change for 61 cents

pick a nickel, we will now have to make change for 57 cents

pick a quarter, we will now have to make change for 37 cents

And then for 61 (first choice from above), we go through the 3 possible choices again for the second coin:

pick a penny, we will now have to make change for 60 cents

pick a nickel, we will now have to make change for 56 cents

pick a quarter, we will now have to make change for 36 cents

We keep doing this recursively until we reach 0.

CODE:

def minCoins(choices, change):

minCoins([1, 5, 25], 62) # should return 6 minCoins([9, 6, 5, 1], 11) # should return 2

Instructions from your teacher 1 2 3 def minCoins(choices, change): Problem mnCoins([1, mnCoins([9, 5, 6, 25], 62) # should return 6 5, Given a set of coin values, we want to find the least number of coins necessary for making a given change where we have an infinite number of each coin value 1], 11) # should return 2 For example, if we have pennies, nickels and quarters (i.e. [1,5, 25), and we are asking what's the minimum number of coins needed to make a change of 62 cents, the answer is 6: two quarters, two nickels, and two pennies Complete the function mincoins() to return the number of minimum coins necessary to make the required change, where the set of possible coin values are given by the choices array Your solution must use Dynamic Programming with memoization :) Hint Since we want to use Dynamic Programming for this problem, we know that it has the optimal sub-structure property. In this case, the mincoins() at each step is the minimum of all possible choices we can make for the given change (i.e. all possible sub-problems). In other words, when we start with our change as 62, we have 3 choices for the first coin: Python 3.6.1 (default, Dec 2015, 13:05:11) [GCC 4.8.2] on linux pick a penny, we will now have to make change for 61 cents pick a nickel, we will now have to make change for 57 cents pick a quarter, we will now have to make change for 37 cents And then for 61 (first choice from above), we go through the 3 possible choices again for the second coin: pick a penny, we will now have to make change for 60 cents e pick a nickel. we will now have to make change for 56 cents