Coin Change DP DSA Solution - Study Chapter | QuizMaker

Coin Change explained with brute force recursion, optimized minimum coins DP, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 8: Dynamic Programming

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.

Input	Output	Why
`coins = [1,2,5], amount = 11`	`3`	11 can be made with 5 + 5 + 1.

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

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int impossible = amount + 1;
        vector<int> dp(amount + 1, impossible);
        dp[0] = 0;

        for (int value = 1; value <= amount; value++) {
            for (int coin : coins) {
                if (value >= coin) {
                    dp[value] = min(dp[value], dp[value - coin] + 1);
                }
            }
        }

        return dp[amount] == impossible ? -1 : dp[amount];
    }
};

class Solution {
    public int coinChange(int[] coins, int amount) {
        int impossible = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, impossible);
        dp[0] = 0;

        for (int value = 1; value <= amount; value++) {
            for (int coin : coins) {
                if (value >= coin) {
                    dp[value] = Math.min(dp[value], dp[value - coin] + 1);
                }
            }
        }

        return dp[amount] == impossible ? -1 : dp[amount];
    }
}

Sample Dry Run

Step	State	Result
dp[0]	0 coins	Base state
dp[1]	coin 1 gives 1	dp[1] = 1
dp[5]	coin 5 gives 1	dp[5] = 1
dp[11]	dp[6] + coin 5	answer = 3

Complexity

Measure	Value	Reason
Time	O(amount * coins)	Every amount tries every coin once.
Space	O(amount)	The dp array stores one answer per amount.

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

Why use amount + 1 as infinity?

You can never need more than amount coins when coin 1 exists, so amount + 1 is safely impossible.

Is this counting combinations?

No. This version finds the minimum number of coins.

What is the core pattern?

Minimum-value bottom-up DP.