Coin Change Problem
The Coin Change Problem finds the minimum number of coins needed to make a given amount using unlimited supplies of given coin denominations. It's a classic example of both dynamic programming and greedy algorithms, with two main variants: finding the minimum number of coins (optimization) and counting the number of ways to make change (counting). This problem has direct applications in currency systems, vending machines, and resource optimization.
Visualization
Interactive visualization for Coin Change Problem
Coin Change Problem
• Time: O(amount × coins)
• Space: O(amount)
• Bottom-up dynamic programming
Interactive visualization with step-by-step execution
Implementation
1function coinChange(coins: number[], amount: number): number {
2 const dp: number[] = Array(amount + 1).fill(Infinity);
3 dp[0] = 0;
4
5 for (let i = 1; i <= amount; i++) {
6 for (const coin of coins) {
7 if (i >= coin) {
8 dp[i] = Math.min(dp[i], dp[i - coin] + 1);
9 }
10 }
11 }
12
13 return dp[amount] === Infinity ? -1 : dp[amount];
14}
15
16// Count number of ways to make change
17function coinChangeWays(coins: number[], amount: number): number {
18 const dp: number[] = Array(amount + 1).fill(0);
19 dp[0] = 1;
20
21 for (const coin of coins) {
22 for (let i = coin; i <= amount; i++) {
23 dp[i] += dp[i - coin];
24 }
25 }
26
27 return dp[amount];
28}Deep Dive
Theoretical Foundation
Coin Change uses dynamic programming with a 1D array dp where dp[i] represents the minimum number of coins needed to make amount i. The recurrence relation is: dp[i] = min(dp[i], dp[i-coin] + 1) for each coin denomination. Base case is dp[0]=0 (zero coins for amount 0). For the counting variant, dp[i] represents the number of ways to make amount i, with recurrence dp[i] += dp[i-coin]. The algorithm builds solutions from smaller amounts, ensuring optimal substructure. Note that greedy approach works only for certain coin systems (like US coins: 1,5,10,25) but fails for arbitrary denominations (e.g., coins=[1,3,4], amount=6: greedy gives 4+1+1=3 coins, optimal is 3+3=2 coins). DP guarantees optimal solution for any coin system.
Complexity
Time
O(n × amount)
O(n × amount)
O(n × amount)
Space
O(amount)
Applications
Industry Use
Vending machine change dispensing systems
Currency exchange and cashier systems
Resource allocation in production planning
Packet scheduling in networking
Knapsack-like problems in operations research
Making change with minimum bills/coins
Budget optimization with discrete spending units
Token systems in gaming and arcade machines
Use Cases
Related Algorithms
0/1 Knapsack Problem
A classic optimization problem where you must select items with given weights and values to maximize total value without exceeding the knapsack's capacity. Each item can be taken only once (0 or 1). This is a fundamental problem in combinatorial optimization, resource allocation, and decision-making scenarios.
Longest Common Subsequence (LCS)
Finds the longest subsequence common to two sequences. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. This is fundamental in diff utilities, DNA sequence analysis, and version control systems like Git.
Edit Distance (Levenshtein Distance)
Edit Distance, also known as Levenshtein Distance, computes the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. Named after Soviet mathematician Vladimir Levenshtein who introduced it in 1965, this fundamental algorithm has applications in spell checking, DNA sequence analysis, natural language processing, and plagiarism detection.
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) finds the length of the longest subsequence in an array where all elements are in strictly increasing order. Unlike a subarray, a subsequence doesn't need to be contiguous - elements can be selected from anywhere as long as their order is preserved. This classic DP problem has two solutions: O(n²) dynamic programming and O(n log n) binary search with patience sorting. Applications include stock price analysis, scheduling, Box Stacking Problem, and Building Bridges Problem.