The coin change problem is one of those classic puzzles that quietly shapes how software thinks about money. Originally a textbook dynamic programming challenge, it has become a surprisingly useful lens for understanding how decentralized exchanges and trade routers find the best path through a maze of token pairs. If you've ever wondered why some swaps feel "smarter" than others, this humble algorithm is part of the answer.

What Is the Coin Change Problem?

At its core, the problem asks a deceptively simple question: given a set of coin denominations and a target amount, what's the minimum number of coins needed to make that amount? If you have coins worth 1, 5, and 10, and you owe 27 cents, the optimal answer is five coins: 10 + 10 + 5 + 1 + 1.

The naive solution is to try every possible combination, which works for tiny inputs but explodes into billions of calculations as the amount grows. Even for a modest target like 1,000 with a dozen denominations, brute force becomes impractical. That's why the coin change problem became a poster child for dynamic programming — a method that breaks a big problem into smaller, overlapping subproblems and stores the answers so you never solve the same one twice.

It's also a favorite on coding interview platforms, where it's commonly listed under "medium" difficulty on LeetCode and similar sites. But the math behind it reaches far beyond whiteboards, especially when you start thinking about money that moves on-chain.

How Dynamic Programming Cracks It

The Recursive Baseline

The straightforward recursive approach calls itself for every coin and every remaining amount. It works, but it's painfully slow — for a target of just a few hundred units, the call tree can balloon into millions of nodes, each redoing work that was already done higher up the stack.

Memoization (Top-Down)

By caching results in a dictionary or array, you only compute each subproblem once. If you've already figured out the optimal coin count for 17 cents, you reuse that answer instead of recalculating it. The recursion still runs, but the cost per call drops to a constant lookup, turning exponential time into polynomial time.

Tabulation (Bottom-Up)

The cleaner approach builds a table from 0 up to the target amount. Each cell holds the minimum coins needed for that value, and the algorithm fills them in order, looking back at smaller amounts to compute larger ones. Time complexity drops to O(amount × number of denominations), which is why this version dominates real-world code. It's also the variant most easily ported to languages without rich recursion support.

The greedy shortcut — always picking the largest coin — works for canonical currency systems like USD, but fails on arbitrary inputs. Try making 6 with coins [1, 3, 4]: the greedy path gives 4 + 1 + 1 (three coins), while the optimal is 3 + 3 (two coins). Dynamic programming handles both cases correctly without any assumption about the denomination set.

Where Crypto Meets the Coin Change Problem

Here's where it gets interesting for blockchain builders. A DEX aggregator has to figure out the best way to swap Token A for Token D across multiple liquidity pools. Pools charge fees and have different depths, so the optimal route isn't obvious — it's essentially a coin change problem in disguise, where "denominations" are token pairs and the "target" is the desired output amount.

Gas costs add another layer. On Ethereum and similar chains, every contract call costs money, so splitting one large trade into many small ones can actually lose value. The algorithm has to balance minimum coin count against minimum gas spend, which is a variation known as the unbounded knapsack problem. The same family of solutions applies.

Limit-order execution bots face the same math. They slice a big order into smaller chunks across exchanges and times, minimizing slippage and fees. The shape of the problem is identical: minimize total cost, subject to constraints, with reusable subcomponents. Even cross-chain bridges borrow this thinking when routing assets across wrapped and native token representations.

Real-World Applications in DeFi and DEX Routing

Protocols like 1inch, Matcha, and ParaSwap all lean on similar optimization logic to pick the cheapest swap path across dozens of liquidity sources. While production code uses more sophisticated heuristics and graph algorithms like Dijkstra's, the foundational idea — decompose, cache, recombine — comes straight from dynamic programming. The coin change problem is the training wheels for that mindset.

Even off-chain tools benefit. Portfolio rebalancing scripts, yield-farming simulators, and arbitrage detectors borrow the same patterns: break a complex optimization into small solvable pieces, store the results, and assemble a final answer. The shape is identical even when the numbers and tokens change.

For developers, the lesson is practical. Mastering the coin change problem isn't just about passing interviews — it's about training your brain to think in optimal decomposition, a skill that shows up everywhere from smart contract design to on-chain game theory. Once you've internalized "small problems, cached answers, big payoff," you start seeing it in MEV bots, liquidations, and gas optimization too.

Key Takeaways

  • The coin change problem finds the minimum number of coins to hit a target amount using given denominations.
  • Dynamic programming — both top-down memoization and bottom-up tabulation — solves it efficiently in polynomial time.
  • Greedy approaches work for standard currencies but fail on arbitrary inputs.
  • DEX aggregators and trade routers apply the same optimization logic to find the cheapest swap paths.
  • Understanding this problem sharpens your intuition for a wide range of on-chain optimization challenges, from MEV to portfolio rebalancing.