Teaching Kids Programming – Dynamic Programming Algorithm to Compute Minimum Number of Coins

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) —