Coin Change

1. Problem Description

Given coins of different denominations and a total amount, write a function to compute the minimum number of coins needed to make up that amount. If no combination of coins can make up the amount, return -1.

You may assume that the number of coins of each denomination is unlimited.

2. Approach

1. Approach 1
   • DFS
   • Essentially the same as Combination Sum
   • The difference is that coins may be selected repeatedly
2. Approach 2
   • DFS + memoization

3. Implementation

3.1. DFS

func coinChange(coins []int, amount int) int {
    minCount := math.MaxInt32
    coniChangeDFS(coins, amount, 0, &minCount)

    if minCount == math.MaxInt32 {
        return -1
    }

    return minCount
}

func coniChangeDFS(coins []int, target int, count int, minCount *int) {
    if target < 0 {
        return
    }

    if target == 0 {
        *minCount = min(*minCount, count)
        return
    }

    for i := 0; i < len(coins); i++ {
        coniChangeDFS(coins, target-coins[i], count+1, minCount)        
    }

}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b

}

3.2. DFS + Memoization

func coinChange(coins []int, amount int) int {
	sort.Slice(coins, func(i, j int) bool {
		return coins[i] > coins[j]
	})
	memo := make(map[int]int, 0)
	minCount := coniChangeDFS(coins, amount, memo)

	if minCount == math.MaxInt32 {
		return -1
	}

	return minCount
}

func coniChangeDFS(coins []int, target int, memo map[int]int) int {
	count, ok := memo[target]
	if ok {
		return count
	}
	count = math.MaxInt32

	if target < 0 {
		return math.MaxInt32
	}

	if target == 0 {
		return 0
	}

	for i := 0; i < len(coins); i++ {
		count = min(count, coniChangeDFS(coins, target-coins[i], memo)+1)
	}

	memo[target] = count
	return count
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b

}

4. References

• Java Recursion + Memoized Search + Dynamic Programming - Coin Change - LeetCode