Coin change (I)

Minimum number of coins needed to obtain a given value

1) Initialize a list that contains the needed number of coins to obtain each value between 0 and the amount

2) Initialize every value to infinity expect for 0 that is initialize to 0

3) Iterate over every available coins

4) Iterate over every value of the list

5) For each value the new minimum number is the minimum between the minimum number and the number of coins needed for the value minus the current coin + 1

6) Return the number of coins needed for last value

def coinChange(coins: List[int], amount: int) -> int:
    coins_needed = [0] + [amount+1 for _ in range(amount)] # list initialization to (a false) inf except 0 to 0
    for coin in coins:
        for i in range(coin, amount+1):
            coins_needed[i] = min(coins_needed[i], coins_needed[i-coin] + 1) # take min coin between current value and (1 + value for i-coin)
    return(coins_needed[-1] if coins_needed[-1] <= amount else -1) # return last value (if inf return -1)