DSA problem
Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.
This is the canonical unbounded-knapsack minimization problem: each coin denomination can be used an unlimited number of times, and we are asked to optimize the count rather than maximize a value. Because reusing items is free, the recurrence has overlapping subproblems and a clean bottom-up dynamic programming formulation.
Define dp[a] as the minimum number of coins needed to assemble exactly amount a. The base case is dp[0] = 0 because zero coins are needed for amount zero. For every other amount, initialize dp[a] to a sentinel meaning "unreachable" (for example amount + 1, which is strictly larger than any feasible answer). The recurrence is dp[a] = min(dp[a], dp[a - coin] + 1) for each coin denomination such that coin <= a.
The optimal order is to iterate the amount a from 1 to amount in the outer loop and the coin denominations in the inner loop, although swapping the two loops also yields a correct minimum-count answer because we are minimizing rather than counting distinct combinations. After filling the table, dp[amount] either holds the minimum coin count or remains the sentinel, in which case we return -1. The algorithm runs in O(amount * len(coins)) time and O(amount) space, a textbook 1D unbounded-knapsack solution.
Examples
coins = [1,2,5], amount = 113coins = [2], amount = 3-1coins = [1], amount = 00Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.