Problem Description
Given an array of coin denominations and an integer amount, determine the minimum number of coins required to make up that amount. If it is impossible to do so with the given coins, return -1. You can use each coin as many times as needed.
Key Insights
- Use a dynamic programming approach to build up a solution from smaller subproblems.
- Define dp[x] as the minimum number of coins required for amount x.
- The recurrence relation is: dp[x] = min(dp[x], dp[x - coin] + 1) for each coin.
- Initialize dp[0] = 0 and set other values to a number larger than the maximum possible coins (amount+1 works as an infinity substitute).
- An alternative approach is through BFS, treating each amount as a node and each coin as an edge, but the DP method is more intuitive here.
Space and Time Complexity
Time Complexity: O(amount * n) where n is the number of coins. Space Complexity: O(amount) for the dp array.
Solution
We use a bottom-up dynamic programming approach. The idea is to use a one-dimensional dp array where each element at index x represents the minimum number of coins required to form the amount x. Starting from dp[0] which is 0, we iterate through all amounts up to the target amount and update dp[x] based on each coin denomination. If after filling the dp array the value dp[amount] remains unchanged (i.e., greater than amount), it means the amount cannot be formed and we return -1.