Coin Change
Description: Given coin denominations and an amount, return the minimum number of coins needed. Coins may be reused. Return -1 if it is impossible.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Example 2:
Input: coins = [2], amount = 3
Output: -1
Constraints:
1 <= coins.length <= 12
0 <= amount <= 10⁴
Recommended time and space complexity
Aim for O(amount × number of coins) time.
Hint 1
A greedy approach fails. Try coins = [1,3,4], amount = 6.
Hint 2
Let dp[i] be the minimum coins for amount i. Which states lead into i?
Hint 3
You reach i from i − c for each coin c, so dp[i] = min(dp[i − c]) + 1.