Min Number Of Coins For Change

Tags

Min Number Of Coins For Change

Category

Dynamic Programming

Difficulty

Medium

Problem Statement

Given a target amount n and an array of positive integer coin denominations, return the minimum number of coins needed to make change for the target amount. Each denomination can be used an unlimited number of times. If it is impossible to make change, return -1.

Intuition

We build a DP table where dp[amount] stores the minimum number of coins needed to make that amount. For each amount, we try every denomination and check if using that coin leads to a better (smaller) count. This is the optimization version of the coin change problem — instead of counting ways, we minimize the number of coins.

Approach

  1. Create an array dp of size n + 1, initialized to infinity (or n + 1 as a sentinel).
  2. Set dp[0] = 0 (zero coins needed to make amount 0).
  3. For each denomination coin:
    • For each amount from coin to n:
      • dp[amount] = min(dp[amount], dp[amount - coin] + 1)
  4. If dp[n] is still infinity, return -1. Otherwise, return dp[n].

Pseudocode

function minCoinsForChange(n, denominations):
    dp = array of size (n + 1) filled with infinity
    dp[0] = 0

    for coin in denominations:
        for amount from coin to n:
            dp[amount] = min(dp[amount], dp[amount - coin] + 1)

    if dp[n] == infinity:
        return -1
    return dp[n]

Time & Space Complexity

  • Time: O(n * d) where n is the target amount and d is the number of denominations.
  • Space: O(n) for the DP array.

Key Insights

  • This is closely related to "Number of Ways to Make Change" but uses min instead of +=.
  • The infinity initialization ensures that unreachable amounts are never used as building blocks.
  • Using n + 1 as the sentinel value works because you can never need more than n coins (even with denomination 1).
  • The order of the nested loops (denominations outer, amounts inner) does not affect correctness for the minimization version, but it is conventional and slightly cleaner.

Edge Cases

  • Target amount is 0: return 0 (no coins needed).
  • No denominations: return -1 for any positive target.
  • The target cannot be formed by any combination of denominations: return -1.
  • Single denomination of 1: answer is always n.
  • Denomination larger than the target: that coin is simply never used.

Linked mentions