Coin Change DP Java | Fresher Interview
Fast recall
Quick revision
Core answer
dp[a] = minimum coins to make amount a. Transition: dp[a] = 1 + min(dp[a - coin]) over all coins <= a. Base dp[0] = 0; initialize the rest to a large sentinel (infinity). Build bottom-up to dp[amount]. O(amount * coins) time, O(amount) space; return -1 if unreachable.Whether you define the dp state, the min-over-coins transition, and the unreachable (-1) case
Greedily picking the largest coin (fails for coins like {1,3,4}, amount 6), or wrong base/sentinel
Explain why greedy fails and how the dp[0]=0 base plus an infinity sentinel handles unreachable amounts
Interview-ready guide
Interview answer
Coin change asks for the minimum number of coins that add up to a target amount.
The first thing I'd point out is why a greedy approach, always grabbing the largest coin that fits, doesn't work in general. With coins one, three, and four, making six greedily gives four plus one plus one, three coins, but the real optimum is three plus three, just two coins. So I use dynamic programming.
I define dp of a as the minimum number of coins needed to make amount a. The transition is: for each amount a, I try every coin that's less than or equal to a, and dp of a is one plus the minimum of dp of a minus that coin.
The one accounts for using that one coin, and dp of a minus coin is the best way to make the remaining amount. The base case is dp of zero equals zero, because it takes no coins to make zero. I initialize all the other entries to a large sentinel value, like amount plus one, which stands in for infinity, meaning unreachable.
Then I fill the table bottom-up from one to the target. At the end, if dp of the amount is still that sentinel, the amount can't be made with the given coins, so I return minus one; otherwise I return dp of amount. The complexity is O of amount times the number of coins, with O of amount space.
One clarification I'd make is that this is the minimum-coins variant; there's a related problem asking for the number of distinct ways to make the amount, which uses a summing transition instead of a min.
Coin Change DP Java | Fresher Interview
Direct Answer
Coin change (min coins): find the fewest coins summing to an amount. Define dp[a] = minimum coins to make amount a. Transition: dp[a] = 1 + min(dp[a - coin]) over all coins <= a. Base dp[0] = 0; initialize the rest to a large sentinel (infinity). Build bottom-up to dp[amount]. O(amount * coins) time, O(amount) space; return -1 if unreachable.
Deep Dive & Architecture
Let dp[a] mean the smallest number of coins needed to make amount a. The known starting point is dp[0] = 0: no coins are needed for zero. Every other cell starts with a sentinel larger than any possible answer.
For each amount, try every coin that fits. If coin c is the final coin used, the earlier part must make a - c, so the candidate answer is dp[a - c] + 1. Keep the smallest candidate.
Worked example: coins [1, 3, 4], amount 6
The table grows as [0, 1, 2, 1, 1, 2, 2]. Amount 4 needs one coin. Amount 5 uses 4 + 1 and needs two. At amount 6, using a 3 looks back at dp[3] = 1, so 3 + 3 gives two coins. This beats the greedy choice 4 + 1 + 1, which uses three coins.
If the target cell still contains the sentinel, the amount is unreachable; for coins [2], amount 3 is such a case and returns -1. The loops examine amount × numberOfCoins combinations, so time is O(amount × coins) and the table uses O(amount) space.
Code Example
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // sentinel = 'infinity'
dp[0] = 0; // base case
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
// coins={1,3,4}, amount=6
// dp: [0,1,2,1,1,2,2] -> dp[6]=2 (3+3), beating greedy's 3 (4+1+1)
Common Mistakes & Pitfalls
- Greedy: picking the largest coin first is wrong for non-canonical coin systems.
- Bad sentinel: use
amount + 1(always > any real answer) sominworks and unreachable is detectable. - Wrong base:
dp[0]must be 0, not the sentinel. - Confusing variants: 'min coins' (this) vs 'number of ways' (different transition, sum not min).
Check your understanding
Answer these without looking back at the article.
- What is dynamic programming and when do you use it?
- What is memoization vs tabulation in DP and which should you use in interviews?
- What is the longest common subsequence (LCS) problem?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.