Abstract / Summary

Find the fewest coins needed to make a certain amount using given coin values.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (6+ million submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic minimum-coin change problem using a bottom-up dynamic programming approach. It builds a one-dimensional table that records the smallest number of coins required to reach each intermediate amount up to the target. The algorithm iterates over reachable amounts and attempts to extend them with each coin denomination, updating the table whenever a better (smaller) count is found. The final answer is read directly from the table entry corresponding to the requested amount.

Key Steps

The initialization creates a DP vector sized for the maximum supported amount and marks all entries as unreachable with -1. The base case for amount zero is explicitly set to zero, establishing the starting point for the recurrence.

vector<int64_t> dp(11000, -1);
dp[0] = 0;

The outer loop walks through every amount from zero up to the target. A guard skips any amount that has not been reached yet, ensuring that only viable states participate in further expansion.

for (int64_t i = 0; i <= amount; i++)
{
    if (dp[i] == -1)
        continue;
    // inner loop follows
}

Inside the outer loop, the inner loop iterates over each coin value. For each coin, it computes the prospective new sum and discards it if it would exceed the target amount. This prevents out-of-bounds accesses and unnecessary work.

for (auto c : coins)
{
    int64_t sum = i + c;
    if (sum > amount)
        continue;
    // update logic follows
}

When a valid new sum is found, the algorithm updates the DP entry. If the entry has never been set (-1), it adopts the count from the current state plus one coin. If the entry already holds a value, the algorithm retains the smaller of the existing count and the newly computed count, guaranteeing that the table always reflects the minimal number of coins discovered so far.

if (dp[sum] == -1)
    dp[sum] = dp[i] + 1;
else
    dp[sum] = min(dp[sum], dp[i] + 1);

Finally, the function returns the DP entry for the requested amount. If the amount is unreachable, the sentinel -1 propagates to the caller, indicating failure.

return dp[amount];

Edge Cases Handled

When the target amount is zero, the DP table entry dp[0] is preset to zero, causing the outer loop to immediately satisfy the condition and return the correct result without further processing.

If a particular coin value is larger than the remaining amount needed, the inner loop’s sum > amount check discards that transition, preventing invalid updates.

Unreachable amounts remain marked with -1 throughout the computation. The final return statement therefore conveys impossibility directly, without requiring additional post-processing.

The use of 64-bit integers for indices and DP values safeguards against overflow when the sum of an intermediate amount and a coin could exceed the range of a 32-bit integer, especially when large coin denominations are present.

Performance Optimizations

The algorithm avoids unnecessary work by skipping DP entries that are still -1. This early-continue pattern reduces the number of inner-loop executions dramatically when many amounts are unreachable early in the process.

By preallocating the DP vector to a fixed size (11000) and initializing it once, the code eliminates repeated memory allocations that would occur with dynamic resizing.

The conditional update distinguishes between first-time assignments and subsequent improvements, allowing the min operation to be invoked only when needed. This selective comparison reduces the total number of arithmetic operations.

Using a single linear DP array rather than a two-dimensional structure keeps the memory footprint compact and improves cache locality, leading to faster access patterns during the nested loops.

Overall, the combination of early pruning, preallocation, and minimal arithmetic yields an implementation that scales efficiently with the size of the input coin set and the target amount.

Imagine you have a big pile of coins and you want to reach a specific total amount of money. This code is like a little robot helper that figures out the smallest number of coins needed to reach that exact total.

First, the robot sets up a long piece of paper with many boxes, and it labels each box with a number starting from zero up to the amount you want to reach. The robot writes a special mark in these boxes to show that it has not visited them yet. Then, the robot starts at the very first box, which represents zero, and says it takes zero coins to have zero money.

The robot looks at every box one by one. If a box has a mark showing the robot has not been there, it skips that box and moves to the next. If the robot has been to the box, it picks up every type of coin you have. For each coin, it adds the value of that coin to the current amount of money. This gives the robot a new total.

If this new total is not more than the final amount the robot is trying to reach, it checks to see if it found a way to get there already. If the robot has not found a way, it remembers how many coins it took to get to that new total. If it has been there before, it compares the number of coins it used now with the number it used before to keep only the smallest count. After checking every single box and every single coin, the robot knows the fewest number of coins needed to reach your total.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		JS		Rust		Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	begeekmyfriend						C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis					JS
	FelixFan1122				C#
	fpdjsns	C++
	fsq		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost									Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru							Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02						C
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666								Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fpdjsns	C++
fsq	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality