This content originally appeared on DEV Community and was authored by Gauri-Khanolkar1
If you’ve ever struggled with dynamic programming, you’re not alone. One of the most famous problems that helped me internalize DP thinking is the Coin Change problem. In this article, I’ll walk you through the problem, how I approached it, and two distinct dynamic programming solutions — top-down with memoization and bottom-up tabulation — including when to use which.
The Problem
Given a list of coin denominations and a target amount, return the minimum number of coins needed to make that amount. If it’s not possible, return -1.
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
This is a classic unbounded knapsack problem because you can use each coin unlimited times.
My Thought Process
My first instinct was to try recursion, but I quickly realized it would be inefficient due to repeated subproblems. That’s when I leaned into memoization (top-down DP) — it fit naturally with the recursive structure.
After that, I also implemented the bottom-up tabulation approach — which avoids recursion altogether and is often more cache-friendly and easier to visualize.
Let’s dive into both.
Top-Down (DFS + Memoization)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# Unbounded knapsack problem
memo = {}
def dfs(amt):
if amt == 0:
return 0
if amt < 0:
return amount + 1 # Invalid large value
if amt in memo:
return memo[amt]
memo[amt] = min(1 + dfs(amt - coin) for coin in coins)
return memo[amt]
result = dfs(amount)
return result if result < amount + 1 else -1
My Comments:
This is a top-down recursive solution with memoization.
We store results for each sub-amount in memo to avoid recomputation.
We return a sentinel value (amount + 1) to represent an invalid path.
It’s memory-efficient and avoids calculating unused subproblems.
Downside: Python’s recursion limit (default = 1000) can cause a RecursionError for large inputs.CPUs are also less efficient at recursion compared to iteration due to stack jumps.
Bottom-Up (Tabulation)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# Bottom-up DP approach
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case
for a in range(1, amount + 1):
for c in coins:
if a - c >= 0:
dp[a] = min(dp[a], 1 + dp[a - c])
return dp[amount] if dp[amount] < float('inf') else -1
My Comments:
This solution uses a DP table (dp[a]) where dp[a] stores the minimum coins for amount a.
It fills the table iteratively from 0 to amount.
No recursion = no stack overflow risk.
Easier to visualize and debug since it builds the solution step-by-step.
Slightly faster in practice due to better cache locality.
Further Reading
This content originally appeared on DEV Community and was authored by Gauri-Khanolkar1