17 / 75
Find minimum coins needed to make amount using unbounded knapsack DP.
Example:
Input:
coins=[1,2,5], amount=11Output:
3 (5+5+1)Common Mistakes:
- Forgetting to initialize dp array with amount+1 (not Integer.MAX_VALUE to avoid overflow)
- Wrong loop order - must iterate coins in outer loop for unbounded knapsack
- Not checking if dp[amount] is still the sentinel value
Notes:
Classic unbounded knapsack. Time O(amount * coins.length), Space O(amount). Alternative: BFS treating each state as a node.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Find minimum coins needed to make amount using unbounded knapsack DP.
Example:
Input:
coins=[1,2,5], amount=11Output:
3 (5+5+1)Common Mistakes:
- Forgetting to initialize dp array with amount+1 (not Integer.MAX_VALUE to avoid overflow)
- Wrong loop order - must iterate coins in outer loop for unbounded knapsack
- Not checking if dp[amount] is still the sentinel value
Notes:
Classic unbounded knapsack. Time O(amount * coins.length), Space O(amount). Alternative: BFS treating each state as a node.
17/75
Coin Change