Coffee Vending Machine Problems [Part 1]

You have a vending machine, but it can not give the change back. You decide to implement this functionality. First of all, you need to know the minimum number of coins for this operation (i'm sure you don't want to return 100 pennys instead of 1$ coin).
So, find an optimal number of coins required, if you have unlimited set of coins with given denominations.

Assume all inputs are valid positive integers, and every set of coin denominations has len 4 for simplicity;

Examples:

optimal_number_of_coins(1, [1, 2, 5, 10]) 
(1 penny) so returns 1  
optimal_number_of_coins(5, [1, 2, 5, 10])
(5) so returns 1
optimal_number_of_coins(6, [1, 3, 5, 10])
(3+3 or 5+1) = 6 so returns 2
optimal_number_of_coins(10, [1, 2, 5, 10]) 
(10) so returns 1
optimal_number_of_coins(12, [1, 3, 5, 10])
(10+1+1) = 12 so returns 3
optimal_number_of_coins(53, [1, 2, 5, 25])
(25+25+2+1) = 53 so returns 4
optimal_number_of_coins(7, [1, 1, 1, 25])
(1+1+1+1+1+1+1) = 7 so returns 7
etc..

Have fun =)

Difficulty: introductory

Starter code:

def optimal_number_of_coins(n, coins):
	

Solutions:
from functools import lru_cache


def optimal_number_of_coins(n, coins):
    @lru_cache(maxsize=None)
    def f(amount: int, idx: int) -> float:
        q, r = divmod(amount, coins[idx])
        if r == 0:
            return q
        elif amount < 0 or idx <= 0:
            return float("inf")
        else:
            return min(1 + f(amount - coins[idx], idx), f(amount, idx - 1))

    coins = sorted(set(coins))
    return f(n, len(coins) - 1)

def optimal_number_of_coins(n, coins):
    s = [0]*(n+1)
    for c in coins:
        if c<=n: s[c]=1
    for i in range(n+1): s[i]=min((s[i-v]+1 for v in coins if i-v>=0),default=0)
    return s[n]

def optimal_number_of_coins(n,coins):
    dicto = {}
    def optimal_number_of_coinss(n, coins,mino = 0,indo = 0):
        key = f"{n}mino:{mino}"
        if key in dicto: return dicto[key]
        if not n: return mino
        if indo >= len(coins) : return 10000
        if n < 0: return 100100
        dicto[key] = min(optimal_number_of_coinss(n - coins[indo],coins,mino + 1,indo) 
                   , optimal_number_of_coinss(n,coins,mino ,indo+1))
        return dicto[key]
    return optimal_number_of_coinss(n, coins)

def optimal_number_of_coins(n,coins):
    dicto = {}
    def optimal_number_of_coinss(n, coins,mino = 0,indo = 0):
        key = f"{n}indo:{indo}mino:{mino}"
        if key in dicto: return dicto[key]
        if not n: return mino
        if indo >= len(coins) : return 10000
        if n < 0: return 100100
        dicto[key] = min(optimal_number_of_coinss(n - coins[indo],coins,mino + 1,indo) 
                   , optimal_number_of_coinss(n,coins,mino ,indo+1))
        return dicto[key]
    return optimal_number_of_coinss(n, coins)

def optimal_number_of_coins(n,A):
    D={}
    for i in range(1,n+1):D[i]=min(-~j+(i+~j*x and D[i+~j*x])for x in A for j in range(i//x))
    return D[n]

def optimal_number_of_coins(n,A):
    D={}
    for i in range(1,n+1):D[i]=min(j+(i-j*x and D[i-j*x])for x in set(A) for j in range(1,i//x+1))
    return D[n]

def optimal_number_of_coins(n, coins):
    return change_making(coins,n)




def _get_change_making_matrix(set_of_coins, r: int):
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
    for i in range(1, r + 1):
        m[0][i] = float('inf')  # By default there is no way of making change
    return m

def change_making(coins, n: int):
    """This function assumes that all coins are available infinitely.
    n is the number to obtain with the fewest coins.
    coins is a list or tuple with the available denominations.
    """
    m = _get_change_making_matrix(coins, n)
    for c in range(1, len(coins) + 1):
        for r in range(1, n + 1):
            # Just use the coin coins[c - 1].
            if coins[c - 1] == r:
                m[c][r] = 1
            # coins[c - 1] cannot be included.
            # Use the previous solution for making r,
            # excluding coins[c - 1].
            elif coins[c - 1] > r:
                m[c][r] = m[c - 1][r]
            # coins[c - 1] can be used.
            # Decide which one of the following solutions is the best:
            # 1. Using the previous solution for making r (without using coins[c - 1]).
            # 2. Using the previous solution for making r - coins[c - 1] (without
            #      using coins[c - 1]) plus this 1 extra coin.
            else:
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])
    return m[-1][-1]

def optimal_number_of_coins(n, a):
    q = [float('inf')] * (n+1)
    q[0] = 0
    for i in range(1, n+1):
        q[i] = min(q[i-x]+1 for x in a if x <= i)
    return q[n]