🪙 Coin Change: Understanding the Problem with Two Dynamic Programming Approaches

Gauri-Khanolkar1 — Thu, 10 Jul 2025 20:48:27 +0000

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

Confession: I’m a Developer Who Just Started Using Git Properly

Gauri-Khanolkar1 — Wed, 25 Jun 2025 19:52:52 +0000

Even after being involved in the field of Computer Science for the past 7 years (as a student and a professional), I am still not as proficient in Git as I would like. This is because I used TortoiseSVN in my previous job.

Why TortoiseSVN Slowed My Git Learning

TortoiseSVN uses a centralized version control system (CVCS) model, where the "trunk" typically represents the main development line or the latest stable version. While it’s great for handling large binary files, it has some limitations:

"Branching" is implemented as directory copies, not as first-class objects
A stable network connection is required to interact with the central repository
Developers do not usually have a full local copy of the repository history

As a result, I rarely needed to think about distributed workflows or advanced branching strategies — two key parts of Git.

Why Git Feels Like a Necessity Now

Git is a distributed version control system (DVCS) that gives each developer a full local copy of the repository. That means:

You can work offline
Branching and merging are fast and flexible
Collaboration scales better across teams

In hindsight, I believe Git is not just better — it’s essential for modern developers.

How I Started Learning Git

Here are two excellent resources that helped me get started:

These gave me both the big picture and the hands-on skills I was missing.

More on Git vs SVN

If you're curious about the differences between the two, this article is a good summary:

👉 SVN vs Git

DEV Community: Gauri-Khanolkar1

🪙 Coin Change: Understanding the Problem with Two Dynamic Programming Approaches

🚨 The Problem

🧠 My Thought Process

✅ Top-Down (DFS + Memoization)

🗒️ My Comments:

🔁 Bottom-Up (Tabulation)

🗒️ My Comments:

📚 Further Reading

Confession: I’m a Developer Who Just Started Using Git Properly

Why TortoiseSVN Slowed My Git Learning

Why Git Feels Like a Necessity Now

How I Started Learning Git

More on Git vs SVN