Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Dynamic Programming (Bottom-Up)

Solution Approach

1. Define a DP Array: Create an array dp where dp[i] represents the minimum number of coins needed to make up the amount i. Initialize this array with a large value (e.g., amount + 1), which is effectively treated as infinity. This represents that initially, each amount is unreachable.
2. Base Case: dp[0] = 0 because zero coins are needed to make the amount zero.
3. Fill the DP Array: For each amount i from 1 to amount, check each coin in the coins array. If using a particular coin does not exceed the amount (i - coin >= 0), update dp[i] as:dp[i]=min⁡(dp[i],dp[i−coin]+1)dp[i] = \min(dp[i], dp[i – coin] + 1)dp[i]=min(dp[i],dp[i−coin]+1)This means that we try to reach the amount i by adding one coin to the minimum coins needed for amount i - coin.
4. Result: After filling the dp array, dp[amount] will hold the minimum number of coins required to make up amount. If dp[amount] is still amount + 1, then it means amount cannot be reached with the given coins, so return -1.

Golang Code

package main

import (
	"fmt"
	"math"
)

func coinChange(coins []int, amount int) int {
	// Initialize dp array with an amount larger than the maximum possible (amount + 1)
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = amount + 1
	}

	// Base case
	dp[0] = 0

	// Fill dp array
	for i := 1; i <= amount; i++ {
		for _, coin := range coins {
			if i - coin >= 0 {
				dp[i] = min(dp[i], dp[i - coin] + 1)
			}
		}
	}

	// If dp[amount] is still amount + 1, return -1
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

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

func main() {
	coins := []int{1, 2, 5}
	amount := 11
	fmt.Println("Output:", coinChange(coins, amount)) // Output: 3

	coins = []int{2}
	amount = 3
	fmt.Println("Output:", coinChange(coins, amount)) // Output: -1

	coins = []int{1}
	amount = 0
	fmt.Println("Output:", coinChange(coins, amount)) // Output: 0
}


//Output: 3
//Output: -1
//Output: 0
//Program exited.

Time and Space Complexity

• Time Complexity: O(amount X len(coins)) because for each amount, we check each coin.
• Space Complexity: O(amount), for the dp array.

Visit https: https://codeandalgo.com for more such contents