📌 Problem Summary

Question page

Given:

• coins[] — denominations (e.g. [1,2,5])
• amount — target value (e.g. 11)

Return:

• Minimum number of coins to make the amount
• If impossible → return -1

---

🧭 Step 1: How to Analyze the Problem

Key signals

• “minimum number of coins” → optimization problem
• Repeated subproblems (e.g. amount 9 appears multiple times)

👉 Ask yourself:

Can I express this problem using smaller subproblems?

---

🔍 Step 2: Try Brute Force Thinking

Define a function:

f(x) = minimum coins needed to make amount x

Then:

f(11) = min(
  f(10) + 1,
  f(9) + 1,
  f(6) + 1
)

General form:

f(x) = min(f(x - coin)) + 1

---

💡 Step 3: Decide the Algorithm

Why NOT greedy?

• Greedy may fail (e.g. coins [1,3,4], amount 6)

Why DP?

• Overlapping subproblems
• Optimal substructure

👉 Decision:

• Use Dynamic Programming

---

🔁 Approach 1: Recursion (Brute Force)

💻 Code

function coinChange(coins: number[], amount: number): number {
    function dfs(remain: number): number {
        if (remain === 0) return 0;
        if (remain < 0) return Infinity;

        let min = Infinity;

        for (const coin of coins) {
            const res = dfs(remain - coin);
            min = Math.min(min, res + 1);
        }

        return min;
    }

    const result = dfs(amount);
    return result === Infinity ? -1 : result;
}

⏱ Complexity

Time: O(k^amount)

• k = number of coins
• Exponential due to repeated work

Space: O(amount)

• Recursion stack depth

❌ Problem

• Same subproblems recomputed many times
• Leads to TLE

🚀 Approach 2: Recursion + Memo (Top-down DP)

💡 Idea

Cache results:

memo[x] = result of f(x)

💻 Code

function coinChange(coins: number[], amount: number): number {
    const memo = new Map<number, number>();

    function dfs(remain: number): number {
        if (remain === 0) return 0;
        if (remain < 0) return Infinity;

        if (memo.has(remain)) {
            return memo.get(remain)!;
        }

        let min = Infinity;

        for (const coin of coins) {
            const res = dfs(remain - coin);
            min = Math.min(min, res + 1);
        }

        memo.set(remain, min);
        return min;
    }

    const result = dfs(amount);
    return result === Infinity ? -1 : result;
}

⏱ Complexity

Time: O(amount × k)

• Each state computed once
• Try all coins per state

Space: O(amount)

• Memo + recursion stack

---

🧱 Approach 3: Bottom-up DP

💡 Idea

• Build from small → big

dp[i] = minimum coins needed for amount i

💻 Code

function coinChange(coins: number[], amount: number): number {
    const dp = new Array(amount + 1).fill(Infinity);

    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

⏱ Complexity

Time: O(amount × k)

Space: O(amount)

---

⚖️ DP vs Backtracking

Problem Type	Technique
Minimum / Maximum	DP
Count ways	DP
All combinations	Backtracking

---

🔥 Similar / Extension Problems

🟢 Core variations

• Coin Change II (518)
• Perfect Squares (279)
• Minimum Path Sum (64)

🟡 Combination / Backtracking

• Combination Sum (39)