Problem Statement
Given an integer array coins representing coins of different denominations and an integer amount, return the fewest number of coins needed to make up that amount. If that amount cannot be made, return -1.
You may assume you have an infinite number of each coin.
Approach
Bottom-up DP: for each amount from 1 to target, find the minimum coins by trying each coin denomination.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(amount * coins) |
| Space | O(amount) |
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: Cannot make 3 with only 2s
Example 3
Input: coins = [1], amount = 0
Output: 0
Constraints
- ▸
1 <= coins.length <= 12 - ▸
1 <= coins[i] <= 2^31 - 1 - ▸
0 <= amount <= 10^4
Loading...
Sign in to run your code...
Asked by companies:
AmazonAppleMicrosoftGoldman Sachs