You have coins of the denominations in coins (an unlimited supply of each) and a target amount. Return the fewest number of coins that add up to exactly amount, or -1 if it cannot be made. Making amount 0 needs 0 coins.
11 = 5 + 5 + 1.- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force recursion tries every coin at every step, which is exponential. Greedy is tempting but wrong: for [1,3,4] and 6 it picks 4 + 1 + 1 (3 coins) while 3 + 3 uses 2. State: dp[a] = minimum coins to make amount a. Recurrence: the last coin is some c, leaving a - c, so dp[a] = min over c of dp[a - c] + 1. Base case: dp[0] = 0, and unreachable amounts stay at infinity. Memoising the recursion gives O(amount * coins), and the bottom-up table fills dp[1..amount] in increasing order with no recursion.
Algorithm
- Create
dpof sizeamount + 1filled with a large value (amount + 1works as infinity), and setdp[0] = 0. - For each
afrom 1 toamount, and each coinc <= a, setdp[a] = min(dp[a], dp[a - c] + 1). - If
dp[amount]is still larger thanamount, return -1. - Otherwise return
dp[amount].
O(amount * coins.length)Space: O(amount)amount + 1 as infinity avoids overflow: with Integer.MAX_VALUE, the expression dp[a - c] + 1 wraps around to a negative number in Java and C++.class Solution: def coinChange(self, coins: List[int], amount: int) -> int: INF = amount + 1 dp = [0] + [INF] * amount # dp[a] = fewest coins for amount a for a in range(1, amount + 1): for c in coins: if c <= a and dp[a - c] + 1 < dp[a]: dp[a] = dp[a - c] + 1 return -1 if dp[amount] > amount else dp[amount]