Given a target amount n and a list (array) of distinct coin values, what’s the fewest coins needed to make the change amount.
For example:
If n = 10 and coins = [1,5,10]. Then there are 4 possible ways to make change:
With 1 coin being the minimum amount.
Implement your solution below:
def rec_coin(target,coins): min_coins = target if target in coins: return 1 else: for value in [ c for c in coins if c<= target]: num_coins = rec_coin(target-value, coins) + 1 min_coins = min(num_coins, min_coins) return min_coins pass
rec_coin(10,[1,5])
2
rec_coin(63,[1,5,10,25])
6
""" RUN THIS CELL TO TEST YOUR FUNCTION. NOTE: NON-DYNAMIC FUNCTIONS WILL TAKE A LONG TIME TO TEST. """ from nose.tools import assert_equal class TestCoins(object): def check(self,solution): coins = [1,5,10,25] assert_equal(solution(45,coins),3) assert_equal(solution(23,coins),5) assert_equal(solution(74,coins),8) print ('Passed all tests.') # Run Test test = TestCoins() test.check(rec_coin)
Recommended: Introduction to Recursion
If you like my post please follow me to read my latest post on programming and technology.
Factory Method is a creational design pattern that deals with the object creation. It separates…
You are given two singly linked lists that intersect at some node. Your task is…
A builder plans to construct N houses in a row, where each house can be…
Find the length of the longest absolute path to a file within the abstracted file…
You manage an e-commerce website and need to keep track of the last N order…
You are given a stream of elements that is too large to fit into memory.…