322. Coin Change

Summary

Compute the minimum number of coins required to reach a given amount. If no combination sums to the target, return -1.

Approach

Use dynamic programming on the amount. The optimal solution for amount x considers every coin c; if x - c >= 0, try using c once plus the best answer for x - c, and keep the minimum count.

Function

Initialization:

dp: array of size N + 1 (where N is the target amount) filled with N + 1, except dp[0] = 0.

For each amount x from 1 to N:

for each coin c in coins:
    if x - c >= 0:
        dp[x] = min(dp[x], dp[x - c] + 1)
return dp[N] if dp[N] != N + 1 else -1

Complexity

Time Complexity: O(NC) where N is the size of the amount, C is the number of coins. Space Complexity: O(N)