Coin Change Problem using Dynamic Programming
We will be solving coin change problem using dynamic programming in Python. This is a medium level problem from Leetcode. We will review two slightly different approaches with one performing a notch better than the other in terms of run time & memory. Let’s get started
Introduction
We have some coins of different values and an amount of money. We need to find the fewest number of coins needed to make up that amount. If it’s not possible to make that amount with the given coins, we will return -1. We assume that we have as many coins as we need.
Example 1: We have coins of values 1, 2, and 5. we need to make up 11. we can do it with 3 coins: two 5-value coins and one 1-value coin.
Example 2: We only have coins of value 2, and we need to make up 3. since we can’t do it with the given coins, so we will return -1.
Example 3: We have coins of value 1, and we don’t need to make up any amount (0). So, we don’t need any coins.
Problem statement
Dynamic programming is helpful in this problem because it allows us to break down the larger problem (finding the minimum number of coins for a given amount) into smaller subproblems (finding the minimum number of coins for smaller amounts) and then combine the solutions of these subproblems to solve the larger problem.
Here’s how dynamic programming can be employed in this solution:
- Initialization: Initialize a list
dpof sizeamount+1and fill it withamount+1. This arraydpstores the minimum number of coins required to make up each amount from 0 to the target amount. Setdp[0] = 0, as it establishes the base case where no coins are needed to make up an amount of 0. - Looping and Updating: We need to iterate through each amount from 1 to the target amount. For each amount, we again need to through each coin available. We will also check if the current coin can be used to make up the current amount. If so, we will update the minimum number of coins needed to make up that amount by considering the minimum between the current value of
dp[amount_temp]and1 + dp[amount_temp - coin], wheredp[amount_temp - coin]represents the minimum number of coins needed to make up the remaining amount after using the current coin. - Final Result: After iterating through all possible combinations, we will check if the minimum number of coins for the target amount is still equal to
amount+1. If it is, it will mean that the target amount cannot be made up with the given coins, so it returns -1. Otherwise, we will return the minimum number of coins required, which is stored indp[amount].
In summary, dynamic programming helps in solving this problem efficiently by breaking it down into smaller subproblems, computing the solution for each subproblem only once, and then combining the solutions to find the optimal solution for the larger problem.
Code
Version 1
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int] # 'coins' is a list of coin denominations
:type amount: int # 'amount' is the total amount of money
:rtype: int # Return the fewest number of coins needed to make
up the amount or -1 if it's not possible
"""
# Create a list 'dp' to store the minimum number of coins
# required for each amount from 0 to 'amount'
# Initialize all values in 'dp' with 'amount + 1' to represent
# an unreachable state
dp = [amount+1] * (amount+1)
# Base case: 0 coins needed to make up 0 amount
dp[0] = 0
# Iterate through each amount from 1 to 'amount'
for amount_temp in range(1, amount+1):
# Iterate through each coin denomination available
for coin in coins:
# Check if the current coin can be used to make up the
# current amount
if amount_temp >= coin:
# Update the minimum number of coins needed to make
# up 'amount_temp'
# by taking the minimum of the current value and 1 +
# the minimum number of coins needed
# to make up the remaining amount after using the
# current coin
dp[amount_temp] = min(dp[amount_temp],
1 + dp[amount_temp - coin])
# Check if the minimum number of coins for the target amount
# is still equal to 'amount + 1'
# If it is, it means that the target amount cannot be made up
# with the given coins, so return -1
if dp[amount] == (1 + amount):
return -1
else:
# Otherwise, return the minimum number of coins required
# to make up the amount
return dp[amount]This solution beats ~82 % of the solutions run time wise and ~54% of the solutions in terms of memory consumption.
We can further optimize this by employing a simple change in the sequence we apply the nested loop. Now, we will first iterate through the coins and then the amounts between coin and the total amount as explained below:
Version 2
# Loop through each coin denomination
for coin in coins:
# Update dp for each amount_temp starting from the value of the
# coin itself
for amount_temp in range(coin, amount+1):
# Check if the current coin denomination can be used
# to make up the current amount_temp
# If it can, update dp[amount_temp] with the minimum between
# its current value and 1 more than
# the minimum number of coins needed to make up the difference
# between amount_temp and the current coin
dp[amount_temp] = min(dp[amount_temp], 1 + dp[amount_temp - coin])with this simple change solution run time improves to beating 93% of the solutions in terms of run time and 75% solutions in terms of memory.
If you liked the explanation , follow me for more! Feel free to leave your comments if you have any queries or suggestions.
You can also check out other articles written around data science, computing on medium. If you like my work and want to contribute to my journey, you cal always buy me a coffee :)
References
[1] Leetcode: https://leetcode.com/problems/coin-change/description/
[2] Dynamic Programming: https://www.geeksforgeeks.org/dynamic-programming/
Comments
Post a Comment