I have written a Python solution here which solves the following problem: how can a given amount of money n be made with the least number of coins of given the denominations d? def min_coin_change(n, d): mini = float("inf") for den in d: diff = n - den if diff == 0: ans = 1 elif diff < 0: ans = float("inf") else: ans = 1 + min_coin_change(n - den, d) mini = min(mini, ans) return mini While my solution works, it takes a very long time when n is larger than 50 or when the length of d is larger than 5. How can I speed up my code so it will work for considerably larger inputs? Am I missing a trick or something which would drastically speed up my code? Continue reading...
