coins lists coin values, and you have as many of each as you like. Return the fewest coins that add up to exactly amount, or -1 if no combination does.
5 + 2 + 2 + 2 = 11. Two fives would leave 1, which no coin can make.
Every sum of 4s and 6s is even.
Constraints
1 <= coins.length <= 121 <= coins[i] <= 2³¹ - 10 <= amount <= 10⁴Let dp[a] be the fewest coins that make amount a, with dp[0] = 0.
Think about the last coin of the best answer. It is one of the coins in coins, say c. Whatever came before it adds up to amount - c, and it must itself be the fewest coins for amount - c. If it weren't, you could swap in a shorter way to make amount - c and beat the best answer.
Time O(amount · k)Space O(amount)
The full walkthrough and code are part of Premium
4