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: