Coins task solution

coins.py

#!/usr/bin/env python3

import sys
import itertools

COINS = [1, 5, 10, 50, 100, 200, 500, 1000, 2500]
CACHE = {}


def change_number(money):
    number = 0
    for current in range(1, money + 1):
        number = change_number_rec(current, 1)

    return number


def change_number_rec(money, min_coin):
    key = f"{money}-{min_coin}"

    if key in CACHE:
        return CACHE[key]
    if money == 0:
        return 1

    result = sum(
        change_number_rec(money - coin, coin)
        for coin in itertools.dropwhile(lambda x: x < min_coin, COINS)
        if money - coin >= 0
    )
    CACHE[key] = result

    return result


def main(num):
    print(change_number(int(num)))


if __name__ == "__main__":
    main(sys.argv[1])