Computes the minimum number of coins from a given denomination set needed to make an exact target amount using bottom-up 1D dynamic programming.
Compact metadata for implementation and discovery.
Unlike greedy coin selection—which fails on non-canonical denominations such as [1, 3, 4] for target 6—bottom-up Coin Change DP evaluates every reachable sub-amount from 1 to target in O(amount * |coins|) time, guaranteeing the globally minimum coin count.
Quick facts
Runtime and memory behavior at a glance.
Best
O(amount * k)
Average
O(amount * k)
Worst
O(amount * k)
Space
O(amount)
Interactive Runtime & Memory Budget Calculator
Estimate wall-clock latency, operation count, and working memory for Coin Change (Minimum Coins DP) across input scales.
428.6 µs
428.6 µs
1.53 MB
dp[s] = 1 + \min_{c \in C,\, c \le s} dp[s - c]Minimum coins to form sum s.
Tested TypeScript and Python 3 implementations paired with unit tests covering edge cases, duplicate keys, and boundary conditions.
/**
* Coin Change Minimum Coins — Bottom-up 1D unbounded knapsack DP
* Time: O(amount * |coins|) | Space: O(amount)
*/
export function coinChangeMin(coins: readonly number[], amount: number): number {
if (amount === 0) return 0;
const dp = new Int32Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}1D state array filling left-to-right as each coin denomination relaxes reachable sums.
Demonstrates why dynamic programming is required when the greedy matroid property does not hold.
What each reference supports for this entry.
Dynamic programming formulation of the change-making problem.
Open sourceGood next jumps from the relationship graph, ranked for useful discovery.
Unbounded forward capacity sweep vs 0/1 reverse capacity sweep.