Coin Change - Dynamic Programming / Coin Change

Problems
1

https://algo.monster/problems/coin_change

2

Slides 7 and 8 say “3-5 < 0”. Should be 4 right?

3

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

4

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;
    }
5

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 :frowning:

6

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

7

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.

8

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
9

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