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.
Given an integer A. Compute and return the square root of A. If A is…
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…
A heap is a specialized tree-based data structure that satisfies the heap property. It is…
What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…
A Binary Search Tree (BST) is a type of binary tree that satisfies the following…