Complexity Analysis
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1What is the time and space complexity?
Work it out before scrolling down.
Time
O(c × a)
Space
O(a)
How to derive it
Outer loop runs c times (number of coin types). Inner loop runs up to a times (amount). Each iteration is O(1) → O(c × a) time. The dp array has a+1 entries → O(a) space. Note: the variables are the number of coin types and the target amount, not the input array size.