Coin Change

Intuition

Let dp[a] be the fewest coins that sum exactly to amount a. The empty amount needs zero coins, so dp[0] = 0, and every other amount starts at infinity to mark it as unreachable until proven otherwise. To make amount a, the last coin used must be some denomination c that is no larger than a, leaving the subproblem a - c; that gives the recurrence dp[a] = min over all valid c of 1 + dp[a - c]. Because every subproblem a - c is strictly smaller than a, computing amounts in increasing order guarantees the values we depend on are already final. If dp[amount] is still infinity at the end, the target cannot be assembled and we return -1.

Algorithm walkthrough

1. 1Create a dp array of size amount + 1 filled with a sentinel that represents infinity, then set dp[0] = 0.
2. 2Iterate a from 1 up to amount, computing the best count for each amount in turn.
3. 3For each amount a, try every coin c with c <= a and consider 1 + dp[a - c] as a candidate.
4. 4Keep the smallest candidate as dp[a], leaving it at infinity when no coin can complete the amount.
5. 5After filling the table, dp[amount] holds the minimum coin count if it is finite.
6. 6Return dp[amount] when it is reachable, otherwise return -1.

Implementation

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        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 dp[amount] if dp[amount] != float('inf') else -1