Coin Change

Given an array of coin denominations coins and an integer amount, return the fewest number of coins needed to make up that amount. If the amount cannot be made, return -1.

Function signature

func CoinChange(coins []int, amount int) int

Example

coins = [1,2,5], amount = 11
output = 3  // 5 + 5 + 1

Constraints

• 1 <= len(coins) <= 50
• 0 <= amount <= 10_000

Notes

• Use DP: dp[a] = min over coins of dp[a-coin] + 1.