Teaching Kids Programming – Dynamic Programming or Greedy Algorithm to Compute the Min Change


Teaching Kids Programming: Videos on Data Structures and Algorithms

Find the minimum number of coins required to make n cents. You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢.

Constraints
0 ≤ n < 2 ** 31
Example 1
Input
n = 3
Output
3
Explanation
You can make this with 3 pennies.

Example 2
Input
n = 5
Output
1
Explanation
You can make this with a 5 cent coin.

Example 3
Input
n = 6
Output
2
Explanation
You can make this with a 5 cent coin and a 1 cent coin.

Hints:
Pay most with the largest denomination and so on.

Compute Minimum Number of Changes by Greedy Algorithm

Because we can always make up the changes using 1 cent, we can greedy choose the largest coin. The greedy strategy works as we can always find solutions for each amount.

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minChange(self, n):
        ans = 0
        for i in (25, 10, 5, 1):
            this = n // i
            ans += this
            n -= this * i
            if n == 0:
                break
        return ans
class Solution:
    def minChange(self, n):
        ans = 0
        for i in (25, 10, 5, 1):
            this = n // i
            ans += this
            n -= this * i
            if n == 0:
                break
        return ans

The above can be implemented using One-liner – trying the coin 25 and then get its remainder and try coin 10 and so on.

1
2
3
class Solution:
    def minChange(self, n):
        return n // 25 + (n % 25) // 10 + (n % 25 % 10) // 5 + (n % 25 % 10 % 5)
class Solution:
    def minChange(self, n):
        return n // 25 + (n % 25) // 10 + (n % 25 % 10) // 5 + (n % 25 % 10 % 5)

The Greedy Algorithms of making change in this problem is O(1) time and O(1) space – as the number of coins is fixed (1, 5, 10 and 25).

Dynamic Programming Algorithms to Make Change

Usin Dynamic Programming Algorithm – we know the DP transition function:

tex_2e39c5ff976e3fe4f0d3513074b81699 Teaching Kids Programming - Dynamic Programming or Greedy Algorithm to Compute the Min Change algorithms dynamic programming python teaching kids programming youtube video for i in [1, 5, 10 and 25].
Given tex_178602f269ae43f25eaa5fd6a9e5ebe3 Teaching Kids Programming - Dynamic Programming or Greedy Algorithm to Compute the Min Change algorithms dynamic programming python teaching kids programming youtube video .

The Bottom Up DP to solve this:

1
2
3
4
5
6
7
8
9
class Solution:
    def minChange(self, n):
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for j in (1, 5, 10, 25):
                if i >= j and dp[i - j] != math.inf:
                    dp[i] = min(dp[i], dp[i - j] + 1)
        return dp[n]
class Solution:
    def minChange(self, n):
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for j in (1, 5, 10, 25):
                if i >= j and dp[i - j] != math.inf:
                    dp[i] = min(dp[i], dp[i - j] + 1)
        return dp[n]

And the Top Down (implemented via Recursion with Memoization aka @cache) is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
 
class Solution:
    def minChange(self, n):
        sys.setrecursionlimit(max(100000, n))
        @cache
        def f(n):
            if n == 0:
                return 0
            if n < 0:
                return math.inf
            ans = math.inf
            for c in (1, 5, 10, 25):
                ans = min(ans, f(n - c) + 1)
            return ans
        return f(n)
import sys

class Solution:
    def minChange(self, n):
        sys.setrecursionlimit(max(100000, n))
        @cache
        def f(n):
            if n == 0:
                return 0
            if n < 0:
                return math.inf
            ans = math.inf
            for c in (1, 5, 10, 25):
                ans = min(ans, f(n - c) + 1)
            return ans
        return f(n)

In Top Down DP, we have to enlarge the recursion limit via sys.setrecursionlimit (to verify using sys.getrecursionlimit).

Both DP algorithms have O(N) time and O(N) space.

See also: Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
660 words
Last Post: Teaching Kids Programming - Sum of Four Numbers using Depth First Search Algorithm
Next Post: How to Mask Email Addresses using PHP Function?

The Permanent URL is: Teaching Kids Programming – Dynamic Programming or Greedy Algorithm to Compute the Min Change

Leave a Reply