Coin Change: Minimum Coins DP Pattern

Learning Outcome

After this lesson, you should be able to define dp[value] as the best answer for a smaller amount and build up to the target.

Problem Statement

Given coin denominations and an amount, return the fewest coins needed to make that amount, or -1 if impossible.

Brute Force Approach

Try every possible coin sequence recursively. The same remaining amounts appear again and again.

Optimized Approach

Use bottom-up DP where dp[value] stores the minimum coins needed for value. Try each coin as the last coin.

Exact Pseudocode

dp[0] = 0
dp[1..amount] = infinity
for value from 1 to amount:
  for coin in coins:
    if value >= coin:
      dp[value] = min(dp[value], dp[value - coin] + 1)
if dp[amount] is infinity:
  return -1
return dp[amount]
  

Reference Code

class Solution:
    def coinChange(self, coins, amount):
        impossible = amount + 1
        dp = [impossible] * (amount + 1)
        dp[0] = 0

        for value in range(1, amount + 1):
            for coin in coins:
                if value >= coin:
                    dp[value] = min(dp[value], dp[value - coin] + 1)

        return dp[amount] if dp[amount] != impossible else -1
  

Sample Dry Run

Complexity

Edge Cases

• amount = 0 should return 0.
• If no combination works, return -1.
• The order of coins does not matter for this minimum-count version.

Interview Checklist

• Use a sentinel larger than any possible answer.
• Never return the sentinel directly.
• Define dp[0] = 0 before filling the table.

FAQs