Solutions

# Top down and bottom up dynamic programming.
# dp

# Top-down DP approach with memoization
# O(amount * len(coins)) time, O(amount) space
# Without memoization: O(len(coins)^amount) time, O(amount) space
def coinChange(coins: list[int], amount: int) -> int:

    def dfs(remaining: int, cache: dict[int, int]) -> int:
        if remaining == 0:
            return 0
        elif remaining in cache:
            return cache[remaining]

        res = 1e9
        for coin in coins:
            if remaining - coin >= 0:
                res = min(res, 1 + dfs(remaining - coin, cache)) 

        cache[remaining] = int(res)
        return int(res)

    mincoins = dfs(amount, {})
    return mincoins if mincoins < 1e9 else -1


# Bottom-up DP approach
# O(amount * len(coins)) time, O(amount) space
def coinChange(coins: list[int], amount: int) -> int:
    dp = [0] + [1e9] * amount

    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount] if dp[amount] < 1e9 else -1