Coin Change

LeetCode 322 · View on LeetCode

Find the minimum number of coins needed to make a target amount. Each denomination can be used unlimited times. Unbounded knapsack with left-to-right iteration.

package main

import "fmt"

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = amount + 1
	}
	dp[0] = 0

	for _, coin := range coins {
		for w := coin; w <= amount; w++ {
			if dp[w-coin]+1 < dp[w] {
				dp[w] = dp[w-coin] + 1
			}
		}
	}

	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

func main() {
	fmt.Println(coinChange([]int{1, 3, 4}, 6))  // 2 (3+3)
	fmt.Println(coinChange([]int{1, 5, 10}, 12)) // 3 (10+1+1)
	fmt.Println(coinChange([]int{2}, 3))          // -1
}