Coin change problem

coin_change.py

import sys
from typing import List


def coin_change(coins: List[int], amount: int) -> int:
    """
    Returns the minimum number of coins required to generate amount.
    Complexity O(amount * len(coins))
    :param coins:
    :param amount:
    :return:
    """
    if amount == 0:
        return 0
    # Set up the amount of coins to -1 (invalid) for all amounts
    coins_per_amount = [sys.maxsize] * (amount + 1)
    # Initial conditions, for the amount of the coins themselves the value is 1
    for coin in coins:
        if coin <= amount: coins_per_amount[coin] = 1
    # Iterate through the all numbers from 2 to amount and find which
    # coin will generate the minimum coin for this amount
    for i in range(2, amount + 1):
        for coin in coins:
            if i > coin and (coins_per_amount[i - coin] + 1 < coins_per_amount[i]
                             or coins_per_amount[i] == sys.maxsize):
                coins_per_amount[i] = coins_per_amount[i - coin] + 1
    return coins_per_amount[amount] if coins_per_amount[amount] < sys.maxsize else -1




if __name__ == '__main__':
    print(coinChange([1, 2, 5], 11))
    print(coinChange([2], 3))
    print(coinChange([5, 10, 25, 50], 75))
    print(coinChange([1], 1))