Medium · Unbounded DP
Understand → Visualise → Practice.
Each state asks for the fewest coins making one amount. Because a denomination may be reused, every coin can extend any smaller reachable state.
dp[x] = 1 + min(dp[x − coin]) over coins no larger than x.
dp[0] = 0; other states are infinity.
Relax dp[x] from dp[x − coin] + 1.
Infinity at the target becomes −1.
O(amount × number of coins) time and O(amount) space.
A greedy largest-coin-first strategy fails for denominations such as [1, 3, 4] and amount 6.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.