Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a list of integers denominations and an integer amount, find the minimum number of coins needed to make amount. Return -1 if there’s no way to make amount.
Constraints
n ≤ 10 where n is the length of denominations.
amount ≤ 500,000.
Example 1
Input
denominations = [1, 5, 10, 25]
amount = 60
Output
3
Explanation
We can make 60 with 2 quarters and 1 dime.Example 2
Input
denominations = [3, 7, 10]
amount = 8
Output
-1
Explanation
We can’t make 8 with any of the denominations given.
The Greedy Algorithm may not work here. For example, given coins [1, 20, 25], and the target is 60, if we greedily pick the most largest coin , we will end up with (25, 25, and 10 times of 1) i.e. 12 coins while the optimal solution will be 3 times 20 i.e. 3 coins.
This problem is like a unbounded knapsack problem, where we can use as many coins of the one type as we want. We can solve this via Depth First Search (Backtracking), and also we can solve this more efficiently using Dynamic Programming Algorithms. In particular, the DP can be classified into Top-Down or Bottom-up.
Unbounded Knapsack Problem via Bottom-up Dynamic Programming Algorithm
Given f(amount) represents the Dynamic Programming function that returns the minimum number of coins require to make changes – we need to iterate through all available coins, and compute the following Dynamic Programming Transition Function:
for all d in all the coins if f(a-d) is reachable.
And initial value
Bottom-up DP initialzes f(0) = 0 and all other values math.inf – and computes the f(1), f(2) until f(amount).
1 2 3 4 5 6 7 8 9 10 | class Solution: def minCoinsRequired(self, denominations, amount): if not denominations: return 0 dp = [0] + [math.inf] * amount for a in range(amount + 1): for d in denominations: if a >= d and dp[a - d] != math.inf: dp[a] = min(dp[a], dp[a - d] + 1) return dp[amount] if dp[amount] != math.inf else -1 |
class Solution: def minCoinsRequired(self, denominations, amount): if not denominations: return 0 dp = [0] + [math.inf] * amount for a in range(amount + 1): for d in denominations: if a >= d and dp[a - d] != math.inf: dp[a] = min(dp[a], dp[a - d] + 1) return dp[amount] if dp[amount] != math.inf else -1
The time complexity is O(AN) where A is the amount and N is the number of coins. The space complexity is O(A).
Minimum Number of Coins via Top-down Dynamic Programming Algorithm
The Top-Down is basically a straightforward implementation of the DP formula but with Recursion + Memoization.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: def minCoinsRequired(self, denominations, amount): @cache def dp(amount): if amount == 0: return 0 ans = math.inf for i in denominations: if i <= amount: x = dp(amount - i) if x != math.inf: ans = min(ans, x + 1) return ans #sys.setrecursionlimit(500000) ans = dp(amount) return ans if ans != math.inf else -1 |
class Solution: def minCoinsRequired(self, denominations, amount): @cache def dp(amount): if amount == 0: return 0 ans = math.inf for i in denominations: if i <= amount: x = dp(amount - i) if x != math.inf: ans = min(ans, x + 1) return ans #sys.setrecursionlimit(500000) ans = dp(amount) return ans if ans != math.inf else -1
Same time complexity O(NA) and same space complexity is O(A). However, due to the limit of number of stack calls from Recursion – this DP may timeout or cause the stack to overflow.
See also: Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
This is very similar to another Unbounded Knapsack Problem which can also be solved using DP algorithms: Teaching Kids Programming – Dynamic Programming Algorithm to Compute Minimum Number of Coins
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: GoLang Programming: N-ary Tree Preorder Traversal Algorithm using Depth First Search
Next Post: Invert a Binary Tree using GoLang
Your algo lesson is great! Thank you for providing such an excellent lesson!
I found a error on page: The link text dosen’t match with link target as follows:
This is very similar to another Unbounded Knapsack Problem which can also be solved using DP algorithms: Teaching Kids Programming – Dynamic Programming Algorithm to Compute Minimum Number of Coins
should change to:
This is very similar to another Unbounded Knapsack Problem which can also be solved using DP algorithms: Teaching Kids Programming – Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
Thank you! Fixed… This is a bug of WP.