# Coin Change - Dynamic Programming / Coin Change

Slides 7 and 8 say â€ś3-5 < 0â€ť. Should be 4 right?

0 makes sense; it means you canâ€™t use 5 when the sum required is 3

Not sure if this fits in the Dynamic Programming theme, but I found a linear solution that worked for the examples (probably a greedy one, that takes advantage of the input being sorted):

``````    public static int coinChange(List<Integer> coins, int amount) {
int nofCoins = 0;
int remaining = amount;

int i = coins.size() - 1;
while (i >= 0 && remaining > 0) {
int currCoin = coins.get(i);
int change = remaining % currCoin;
int currCoinsChange = remaining / currCoin;

if (currCoinsChange > 0) {
nofCoins += div;
remaining = currCoinsChange;
}
i--;
}

if (remaining > 0) {
return -1;
}
return nofCoins;
}
``````

Nevermind, disregard my previous comment. It doesnâ€™t work for test-cases like `[83, 186, 408, 419]` (and there are some copy paste errors above as well). I wish I could delete

Needs more test cases. Ex:
83 186 408 419
6249

Im confused by the DFS+memoization solution. Before you make the recursive call, you set memo[0] = 0. But then you call the function min_coins with a sum of zero. So once the code hits the line â€śif memo[sum] != inf:â€ť it will immediately return 0 since you set memo[0] = 0 before you called the function in the first place. So your code returns 0 everytime.

If weâ€™re looking for a solution closest to the root (i.e. min number of coins), shouldnâ€™t we be using BFS? Something like this:

``````from typing import List
from collections import deque

def coin_change(coins: List[int], amount: int) -> int:
visited = set()

# Initialize a queue to zero
queue = deque([0])
num_coins = 0

# BFS
while len(queue) > 0:
n = len(queue)

for _ in range(n):
# Pop next sum
sm = queue.popleft()

# If sum is the target, return number of coins
if sm == amount: return num_coins

# Add eligible children to queue
for coin in coins:
if (sm, coin) not in visited and (coin, sm) not in visited:
visited.add((sm, coin))

next_sum = sm + coin
if next_sum <= amount:
queue.append(next_sum)

# Track coins used
num_coins += 1

return -1
``````

Actually, youâ€™re onto something. The greedy algorithm actually works correctly for certain denominations, but itâ€™s quite tricky to determine for which ones:

1 Like