Coin Change
Problem Description
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 <= 12
- 1 <= coins[i] <= 231 - 1
- 0 <= amount <= 104
Solve it on LeetCode
Approaches
1. Brute Force - Recursive
The brute force approach is to try all possible combinations of coins to determine the minimum number needed for the given amount. The intuition is to recursively subtract each coin from the amount and solve the problem for the reduced amount until the amount is 0. This tries out all possible combinations.
Code:
- Time Complexity: O(S^n) where S is the amount and n is the number of coins, as we explore all possibilities.
- Space Complexity: O(S) due to the recursion stack.
2. Dynamic Programming - Top Down (Memoization)
To optimize the recursive solution, we use memoization to store the results of subproblems to avoid redundant calculations. The idea is the same as the recursive approach but with a cache to store previously computed results.
Code:
- Time Complexity: O(S * n) where S is the amount and n is the number of coins.
- Space Complexity: O(S) for the memoization table.
3. Dynamic Programming - Bottom Up (Tabulation)
The most efficient approach uses dynamic programming with a bottom-up technique by creating a table to store the minimum coins required for all values from 0 to the amount. We build the solution iteratively.
Code:
- Time Complexity: O(S * n) where S is the amount and n is the number of coins.
- Space Complexity: O(S) for the DP table.