How to Solve the Coin Change Problem Using Dynamic Programming

The problem is illustrated with a bag‑filling analogy: a bag of fixed capacity represents the target amount, and packages of various sizes represent coin denominations. Some packages are too large, some fit exactly, and some require multiple small packages to fill the bag, mirroring the constraints of the coin change problem.

DP Formulation

Define dp[i] as the minimum number of coins needed to make amount i. The recurrence considers each coin coins[j]: if i - coins[j] >= 0, then dp[i] = min(dp[i], dp[i - coins[j]] + 1). The +1 accounts for the selected coin.

To handle the base case, initialize every entry of dp with a sentinel value amount + 1, which is larger than any possible answer (using only 1‑unit coins). Set dp[0] = 0 because zero amount requires no coins.

Algorithm

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for k := range dp {
        dp[k] = amount + 1 // sentinel for "infinite"
    }
    dp[0] = 0

    for i := 1; i <= amount; i++ { // iterate amounts
        for j := 0; j < len(coins); j++ { // try each coin
            if i-coins[j] >= 0 {
                dp[i] = min(dp[i], dp[i-coins[j]]+1)
            }
        }
    }
    if dp[amount] == amount+1 { // unreachable
        return -1
    }
    return dp[amount]
}

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

The outer loop builds solutions from amount 1 up to the target, while the inner loop evaluates every coin denomination. After filling the table, if dp[amount] still equals the sentinel, the amount cannot be formed and the function returns -1; otherwise it returns the minimal coin count.

This step‑by‑step DP approach guarantees the optimal solution because each sub‑problem dp[i] is solved using already optimal sub‑solutions for smaller amounts.