Repository navigation
LC 322. Coin Change (Medium)
- https://leetcode.com/problems/coin-change/
- Dynamic Programming, BFS
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Inspired by 'Programming Interview Problems: Dynamic Programming by Leonardo Rossi' chapter 3
The first solution to gain insight is the recursive solution. But even with memoization that runs too slow.
from functools import lru_cache
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
@lru_cache()
def top_down_recursion(amount):
# Edge cases
if not amount: return 0 # done
if amount < 0: return float('inf') # punish negative payments
optimal_result = float('inf')
for coin in coins:
partial_result = top_down_recursion(amount - coin)
candidate = partial_result + 1 # used one extra coin
optimal_result = min(optimal_result, candidate)
return optimal_result
result = top_down_recursion(amount)
if result == 0: return -1 # indicates payment not possible
return resultBecause of the BFS the first path will be the shortest. It also ignores values that are already in the queue. For example, given coins [1, 2, 5]; on the second level 5 + 2 is ignored because 2 and 5 are already in the queue.
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
from collections import deque
# Store Change, Search depth.
# Search depth is the number of coins
# Provide an initial case for zero change
coin_change_depth = {0: 0}
# Build up a BFS queue of coin combinations
# Start with zero paid (adding a node to tree)
coin_combinations = deque([0])
while coin_combinations:
coin_change = coin_combinations.popleft()
# BFS: the match was reached via the shortest path
if coin_change == amount:
return coin_change_depth[amount]
for coin in coins:
next_payment = coin_change + coin
# Skip overshoot payments
# End case in recursion
if next_payment > amount: continue
# Skip payments already made
# via a previous BFS coin change route
if next_payment in coin_change_depth: continue
# Add the current change and depth to the dict
# And add this to the queue of payment possibilities
coin_change_depth[next_payment] = coin_change_depth[coin_change] + 1
coin_combinations.append(next_payment)
return -1 # No combination could reach the result Runtime: 196 ms, faster than 30.77%
/**
-
@param {number[]} coins
-
@param {number} amount
-
@return {number} */ var coinChange = function(coins, amount) {
// store change and depth // the depth is the number of coins // initial case is zero change with zero coins let coin_change_depth = {0: 0} // BFS Queue let bfs_coin_queue = [0]
while (bfs_coin_queue.length) { let coin_change = bfs_coin_queue.shift()
// Reached amount via bfs, guaranteed least nr coins if (coin_change === amount) return coin_change_depth[amount] for (const coin of coins) { let next_payment = coin_change + coin // skip overshoot if (next_payment > amount) continue // skip payments already tried (part of BFS) if (next_payment in coin_change_depth) continue // append the dict and queue coin_change_depth[next_payment] = coin_change_depth[coin_change] + 1 bfs_coin_queue.push(next_payment) }} return -1 };
This slow result needs examination!