You need to find the minimum number of coins required to make up a given amount from an unlimited supply of given coin denominations. Which algorithmic approach guarantees an optimal solution for this problem?
AGreedy algorithm that picks the largest coin first until the amount is reached
BDynamic programming using a 1D array to store minimum coins needed for all amounts up to the target
CPure brute force recursion trying all combinations without memoization
DSorting coins and using binary search to find the best coin for each sub-amount
Step-by-Step Solution
Solution:
Step 1: Understand problem constraints
The problem requires minimum coins for any amount with unlimited coin usage, which fits unbounded knapsack pattern.
Step 2: Identify algorithm that guarantees optimality
Greedy fails for some coin sets; brute force is correct but inefficient; DP with 1D array efficiently computes minimum coins for all sub-amounts ensuring optimality.
