Algorithmic Toolbox : Money Change Again Problem (WEEK 5)

Programming Assignment 5: Dynamic Programming 1 - Money Change Again

# -------------------------Money Change Again----------------------------

# As we already know, a natural greedy strategy for the change problem does not work correctly for any 
# set of denominations. For example, if the available denominations are 1, 3, and 4, the greedy 
# algorithm will change 6 cents using three coins (4 + 1 + 1) while it can be changed using just two coins (3 + 3). 
# Your goal now is to apply dynamic programming for solving the Money Change Problem for
# denominations 1, 3, and 4.


# Problem Description

# Input Format. Integer money.

# Output Format. The minimum number of coins with denominations 1, 3, 4 that changes money.

# Constraints. 1 ≤ money ≤ 103
# .
# Sample 1.
# Input:
# 2
# Output:
# 2
# 2 = 1 + 1.
# Sample 2.
# Input:
# 34
# Output:
# 9
# 34 = 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4.

Money Change Again : Solution in Python 

import math
values = [134]
m = int(input())
minimum_coins = [0] + [math.inf]*m
for i in range(1, m+1):
    for j in values:
        if i>=j:
            coins = minimum_coins[i-j]+1
            if coins < minimum_coins[i]:
                minimum_coins[i] = coins

print(minimum_coins[m])