You are given an integer array coins representing coin denominations, and an integer amount representing a total amount of money.
Return the fewest number of coins needed to make up the given amount.
If it is not possible, return -1.
You may use unlimited coins of each denomination.
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
Use DP:dp[x] = min(dp[x], dp[x - coin] + 1) for all coins.
Initialize dp[0] = 0, others = INF.
Answer is dp[amount] or -1 if unreachable.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for these companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
