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.
Tags
- dsa
- dynamic-programming
- minimum coins dp