Q94: Coin Change. - DSA Patterns (Multi-Lang)

In Simple Words: Bottom-up DP: dp[a] is min coins to make amount $a$. For each amount from 1 to amount, test each coin: dp[a] = min(dp[a], 1 + dp[a - coin]).

Time: $O(\text{amount} \cdot N)$ | Space: $O(\text{amount})$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def coinChange(coins: list[int], amount: int) -> int:
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], 1 + dp[a - c])
    return dp[amount] if dp[amount] != amount + 1 else -1