Coin Change
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.
Constraints:
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
Input Format:
- An integer array coins representing the available coin denominations
- An integer amount representing the total amount of money
Output Format:
- An integer representing the fewest number of coins needed to make up the amount, or -1 if not possible
Examples:
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
Explanation:
It is not possible to make the amount 3 with the given coins.
Example 3:
Input:
coins = [1], amount = 0
Output:
0
Explanation:
No coins are needed to make the amount 0.
Example 4:
Input:
coins = [1,3,4,5], amount = 7
Output:
2
Explanation:
7 = 3 + 4
Solutions
Dynamic Programming (Bottom-Up) Approach
Use a bottom-up dynamic programming approach to build solutions for smaller amounts and work up to the target amount.
BFS (Breadth-First Search) Approach
Treat the problem as finding the shortest path from 0 to the amount, where each step represents using a coin.
Dynamic Programming with Memoization (Top-Down) Approach
Use recursion with memoization to solve the problem from the target amount down to smaller amounts.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Bottom-Up Dynamic Programming Approach:
- Initialize dp array: [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
- Process coin = 1:
- dp[1] = min(∞, 1 + dp[0]) = min(∞, 1 + 0) = 1
- dp[2] = min(∞, 1 + dp[1]) = min(∞, 1 + 1) = 2
- ...
- dp[11] = min(∞, 1 + dp[10]) = min(∞, 1 + 10) = 11
- dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
- Process coin = 2:
- dp[2] = min(2, 1 + dp[0]) = min(2, 1 + 0) = 1
- dp[3] = min(3, 1 + dp[1]) = min(3, 1 + 1) = 2
- ...
- dp[11] = min(11, 1 + dp[9]) = min(11, 1 + 5) = 6
- dp = [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
- Process coin = 5:
- dp[5] = min(3, 1 + dp[0]) = min(3, 1 + 0) = 1
- dp[6] = min(3, 1 + dp[1]) = min(3, 1 + 1) = 2
- ...
- dp[11] = min(6, 1 + dp[6]) = min(6, 1 + 2) = 3
- dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
- Final result: dp[11] = 3, which means we need 3 coins to make amount 11
Hints
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the dynamic programming table as it is filled, showing how the minimum number of coins is calculated for each amount.
Key visualization elements:
- current coin
- current amount
- dp table updates
Implementation Notes
This is a classic dynamic programming problem that can be approached in multiple ways. The key insight is to build up solutions for smaller amounts and reuse them to solve the larger problem. The bottom-up approach is generally more efficient as it avoids the overhead of recursion.