Coin Change
The problem
Given positive coin denominations and a nonnegative amount, find the fewest coins needed to make that amount with unlimited copies. Return −1 when it is impossible.
Example
coins = [1, 4, 6], amount = 8 → 2
Need a hint?
The best solution for a total can extend a smaller reachable total by one coin.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Initialize dp[0] = 0 and other entries to an unreachable sentinel. For each total from 1 to amount, consider each coin no larger than the total and minimize dp[total−coin] + 1. Return −1 if the target is still unreachable.
Complexity
O(amount × number of denominations) time and O(amount) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.