Dynamic Programming: Minimum Coins Challenge
Find the minimum number of coins needed to make a specific target amount
Problem
Given an array of coins[] of size n and a target value sum, where coins[i] represent the coins of different denominations. You have an infinite supply of each of the coins. The task is to find the minimum number of coins required to make the given value sum. If it is not possible to form the sum using the given coins, return -1.
This naturally invites:
A naive top‑down recursion.
A memoized top‑down Dynamic Programming (DP).
A bottom‑up tabulation DP.
A greedy solution you can analyze and reject.
Examples
Input: coins[] = [25, 10, 5], sum = 30
Output: 2
Explanation : Minimum 2 coins needed, 25 and 5
Input: coins[] = [9, 6, 5, 1], sum = 19
Output: 3
Explanation: 19 = 9 + 9 + 1
Input: coins[] = [5, 1], sum = 0
Output: 0
Explanation: For 0 sum, we do not need a coin
Input: coins[] = [4, 6, 2], sum = 5
Output: -1
Explanation: Not possible to make the given sum.
Hints
Try to define
f(x)that depends on smallerx.Can you reuse results of
f(x)instead of recomputing?
How to participate
Post your solution as a comment (or link a gist) by April 16, 2026 at noon Pacific Time
Include:
Your language
Brief explanation of your approach
Stated complexity
If you feel ambitious, compare a memoized recursive solution vs a bottom‑up iterative one in terms of complexity and stack‑overflow risk.
What I’ll do
By April 18, I’ll publish a Review & Lessons post with:
Annotated feedback on selected submissions
A clean reference solution
Notes on how an interviewer would evaluate your approach.
If you’re short on time this week, at least sketch your approach in prose—that’s still valuable practice.
© The Coding Interview Gym | paulepps.substack.com
@psiro -
Did you look at the review post for this challenge: https://paulepps.substack.com/p/review-and-feedback-coin-change-and
You're using a Greedy algorithm, which works for canonical coin values, e.g. [1, 5, 10, 25], and as it happens, it also works for all the test cases you've chosen.
Try coins = [1, 20, 25] and amount = 40 and greedy fails hard. You're taking the highest denomination first, so it takes 25, then can’t make 15 with {20, 25}, so falls back to fifteen 1s = sixteen coins. The optimal is two 20s = two coins.
To make this work for arbitrary coin denominations, you need dynamic programming.
Great page.
On the assumption that late is better than never, here is my contribution to the conversation.
I could not see the merit of the solutions you recommended. 3 coins = 3 iterations. I did not see recursion / memory in the solution, perhaps I am missing something. But I read this page during 'coding time' just before midnight, so gave it a stab.
In python :
def countcoins(coins , targetsum):
....'''
....Returns the minimum number of coins required to make the given value sum
....Todo : Defence against unexpected input & hints
....:param coins: The coins to be considered
....:param targetsum: The sum to make with specified coins
....'''
....countcount = 0
....running_total = targetsum
....coins.sort(reverse=True) #so we consider them highest coin first
....for coin in coins:
........countcount += int(running_total//coin)
........running_total = running_total%coin
........if not running_total:
............break
....if running_total == 0:
........return countcount
....else:
........return -1
----------------
running_total = targetsum is about readability
if not running_total is about ...why not. == 0 is the same.
----------------
Usage
print(countcoins([25, 10, 5],30))
print(countcoins([9, 6, 5, 1],19))
print(countcoins([5, 1],0))
print(countcoins([4, 6, 2],5))