Problem Statement
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1
- Input:
coins = [1,2,5], amount = 11
- Output:
3
- Explanation:
11 = 5 + 5 + 1
Example 2
- Input:
coins = [2], amount = 3
- Output:
-1
Example 3
- Input:
coins = [1], amount = 0
- Output:
0
Constraints
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4
Approach
Brute Force (Recursive)
Steps:
-
Understand the Problem:
- You need to find the minimum number of coins that sum up to the given amount.
- You can use each coin denomination as many times as needed.
- If it’s not possible to make up the amount with the given coins, return
-1.
-
Identify Choices:
- For each coin, decide whether to include it in the current combination.
- Including a coin reduces the remaining amount by the coin’s value.
- The goal is to minimize the number of coins used.
-
Recursive Exploration:
- At each step, iterate through the coins and recursively attempt to make up the remaining amount after choosing a coin.
- Keep track of the minimum number of coins required.
-
Base Cases:
- If the remaining amount is
0, return 0 (no coins needed).
- If the remaining amount is negative, return a large number (e.g.,
Infinity) to indicate an invalid path.
-
Implementation:
- Implement a recursive helper function that explores all possible combinations of coins.
- Return the minimum number of coins found or
-1 if it's not possible.
Time & Space Complexity:
- Time Complexity: O(S^n)
Where S is the amount and n is the number of coins. The recursion explores all combinations.
- Space Complexity: O(S)
The recursion stack can go as deep as the amount.
Code Snippet:
Dry Run:
Let's perform a dry run for coins = [1,2,5], amount = 5.
In this case, choosing the coin 5 directly gives the minimum number of coins needed.
b. Optimized Approach (Dynamic Programming - Memoization)
Steps:
-
Understand the Problem:
- Same as brute force, but aim to optimize by avoiding redundant calculations.
-
Identify Overlapping Subproblems:
- The brute force approach recalculates the same subproblems multiple times.
- For example, calculating
helper(3) might be repeated in different branches.
-
Memoization:
- Use a memo object to store the results of subproblems.
- Before computing the result for a subproblem, check if it's already in the memo.
- If it is, return the stored value instead of recalculating.
-
Implementation:
- Modify the brute force recursive function to include a memoization mechanism.
- Store the minimum number of coins needed for each sub-amount in the memo.
Time & Space Complexity:
- Time Complexity: O(S * n)
Where S is the amount and n is the number of coins. Each sub-amount is computed once for each coin.
- Space Complexity: O(S)
The memo object stores results for each sub-amount up to S, and the recursion stack can go as deep as S.
Code Snippet:
Dry Run:
Let's perform a dry run for coins = [2, 5], amount = 5.
In this case, choosing the coin 5 directly gives the minimum number of coins needed.
Complexity Analysis
Conclusion
When tackling problems like Coin Change, it's essential to choose the right approach to ensure efficiency and correctness.
Key Takeaways:
- Brute Force methods are straightforward and useful for small input sizes or as a starting point to understand the problem.
- Dynamic Programming (Memoization) enhances the brute force approach by eliminating redundant computations, making it suitable for larger and more complex problems.
- Always assess whether a problem has an optimal substructure and overlapping subproblems, which are indicators that Dynamic Programming can be effectively applied.
- Choosing the right problem-solving technique ensures efficient and effective solutions, paving the way for tackling more complex challenges with confidence.