204. Coin Change - Minimum Number of Coins

Given n coin denominations (unlimited supply of each) and a target amount, find the minimum number of coins needed to make exactly that amount, or print -1 if it can't be made.

Input: Three lines: n (number of denominations); n space-separated denominations; the target amount. Output: Print a single integer - the minimum number of coins to make the amount exactly, or -1 if it's impossible.

1 <= n <= 100, 0 <= amount <= 10^5

This is the MINIMIZATION sibling of 'Coin Change - Count Number of Ways' - despite sounding similar, they need genuinely different DP structures (this one takes a MIN over coin choices per amount; the counting version processes coins one at a time across all amounts to avoid overcounting).

Find the minimum number of coins needed to make a target amount, with unlimited supply of given denominations. Brute force: Try every possible combination of coins directly (recursively including/excluding each denomination any number of times) - this recomputes the SAME sub-amounts repeatedly, causing exponential blowup without memoization. Optimised: Since dp[a] only depends on smaller sub-amounts (a minus some coin value), building the table bottom-up ensures every sub-amount's minimum is computed exactly once and reused directly by all larger amounts that need it.

Recursively try every coin denomination at each step, subtracting it from the remaining amount and recursing, taking the minimum number of coins over all choices that eventually reach exactly zero, and treating a negative remainder or exhausted attempts as impossible. This mirrors the problem definition exactly, but without any caching, the same remaining-amount subproblem gets explored again and again through different combinations of coin choices, causing exponential growth in the number of recursive calls. Time: exponential Space: O(amount)

Fill an array dp[0..amount] iteratively from smallest to largest, where dp[0] = 0 and dp[a] is the minimum over all denominations c <= a of 1 + dp[a - c], reading previously computed smaller entries directly instead of recursing. This computes exactly the same values as the memoized version, but with amount allowed up to 10^5, a recursive solution risks overflowing the call stack on that much recursion depth, whereas the iterative bottom-up version has no such risk and also avoids the overhead of function calls entirely. Time: O(n*amount) Space: O(amount)

Use the same recursive structure as brute force, trying every denomination at each remaining amount, but cache the minimum number of coins needed for each distinct remaining amount the first time it is computed. Since there are only 'amount + 1' distinct remaining-amount subproblems, caching collapses the exponential recursion tree of brute force down to a linear number of unique subproblems, each taking O(n) work to try all denominations. Time: O(n*amount) Space: O(amount)

1. dp[a] = minimum coins needed to make amount a; dp[0]=0. 2. For each amount a, try every coin c <= a: dp[a] = min(dp[a], dp[a-c] + 1). 3. If dp[amount] remains unreachable after filling the table, print -1.

Time: O(n * amount) - for each of the amount values, trying all n coin denominations. Space: O(amount), for the dp array.

Test amount = 0 (0 coins needed), an amount that can't be formed from the given denominations (print -1), and amount = 10^5 (upper bound) for the DP array's size.

Be ready to explicitly note that greedy (always use the largest coin that fits) does NOT always give the minimum for ARBITRARY denomination sets (e.g. {1,3,4} for amount 6: greedy gives 4+1+1=3 coins, but optimal is 3+3=2) - this is exactly why DP, not greedy, is needed in general.