010 — Coin Change

Source

• Original source: Classic unbounded-knapsack minimization exercise
• Platform: LeetCode — https://leetcode.com/problems/coin-change/
• Topic: dynamic programming
• Difficulty: Medium
• Pattern: Unbounded knapsack (min)
• Basic idea inherited from: #3 Min Cost Climbing Stairs — কিন্তু একটা amount-এর উপর min, আর memo-র জন্য hashing

1. Problem in simple words

কতগুলো coin-এর মান দেওয়া (coins), প্রত্যেকটার supply অসীম — যত খুশি ব্যবহার করতে পারো। আর একটা target amount দেওয়া। সবচেয়ে কম কয়টা coin দিয়ে ঠিক amount-টা বানানো যায় বের করো। কোনোভাবেই না বানানো গেলে -1 return করো।

coins = [1, 3, 4], amount = 6
greedy (সবচেয়ে বড় আগে): 4 + 1 + 1 = 3 টা coin
সঠিক DP উত্তর         : 3 + 3 = 2 টা coin   <- greedy fail করে!

2. Which basic idea does this inherit from?

ভিত্তি #3 Min Cost Climbing Stairs-এর "পেছনের ছোট state থেকে min নাও" চিন্তা — কিন্তু সেখানে পেছন ঠিক দুই ঘর ছিল, এখানে পেছন প্রতিটা coin-এর মান অনুযায়ী (a - c)। আরেকটা যোগ: amount বড় হতে পারে আর state-গুলো দরকার অনুযায়ী visit হয়, তাই memoization-এ hashing (dict) লাগে — যেভাবে #5/folder 05-এ hashing শিখেছিলে।

3. What is the hidden math or logic?

লুকানো logic একটাই প্রশ্ন: শেষে কোন coin বসালাম? যদি শেষ coin c হয়, তাহলে তার আগে আমাকে amount a - c বানাতে হয়েছিল — সেটার সবচেয়ে কম coin-সংখ্যার সাথে এই একটা coin যোগ। সব সম্ভব শেষ coin-এর উপর min নিলে globally best পাওয়া যায়। Greedy একটা coin-এ commit করে ফেলে বলে fail করে; DP প্রতিটা শেষ coin-এর history বিবেচনা করে।

4. Which data structure is needed?

একটা 1D array dp (size amount + 1), যেখানে dp[a] = ঠিক amount a বানাতে দরকারি minimum coin-সংখ্যা। Top-down করলে একটা dict (memo) — amount → answer।

5. Why this data structure fits

State একটামাত্র সংখ্যা: কত amount বানানো বাকি/হয়েছে। তাই amount-কে index ধরা flat array নিখুঁত — dp[a] ঠিক amount a-র উত্তর ধরে। Unbounded supply মানে একই coin বারবার নেওয়া যায়, তাই transition একই array-র ছোট index (a-c) পড়ে — কোনো item-dimension লাগে না, এক মাত্রাই যথেষ্ট।

6. Real-life analogy

ভাবো দোকানে ঠিক amount টাকা দিতে হবে, পকেটে অসীম সংখ্যক কিছু নির্দিষ্ট মানের কয়েন। তুমি চাও যত কম কয়েন গুনতে হয়। প্রতিটা সম্ভাব্য "শেষ কয়েন"-এর জন্য ভাবো: "এই কয়েনটা শেষে দিলে বাকি টাকাটা সবচেয়ে কম কয়েনে কীভাবে দিতাম?" — তারপর সব বিকল্পের মধ্যে সবচেয়ে কম-কয়েনের রাস্তাটা বেছে নাও।

7. Visual explanation

dp[a] = amount a-র জন্য min coins। coins = [1, 3, 4], amount = 6:

a    :  0   1   2   3   4   5   6
dp[a]:  0   1   2   1   1   2   2

dp[a] = 1 + min( dp[a - c]  for each coin c <= a )

dp[0] = 0                                  (base)
dp[1] = 1 + dp[0]                  = 1     (1)
dp[2] = 1 + dp[1]                  = 2     (1+1)
dp[3] = 1 + min(dp[2], dp[0])     = 1     (3)
dp[4] = 1 + min(dp[3], dp[1], dp[0]) = 1  (4)
dp[5] = 1 + min(dp[4], dp[2], dp[1]) = 2  (4+1 বা 3+1+1? min=2)
dp[6] = 1 + min(dp[5], dp[3], dp[2]) = 1 + min(2,1,2) = 2   <- answer (3+3)

প্রতিটা amount-এ সব coin "শেষে বসিয়ে" দেখি, ছোট subproblem-এর min + 1 নিই। উত্তর dp[6] = 2।

8. Example input and output

Input : coins = [1,3,4], amount = 6   -> Output: 2   (3+3)
Input : coins = [1,2,5], amount = 11  -> Output: 3   (5+5+1)
Input : coins = [2], amount = 3       -> Output: -1  (বানানো অসম্ভব)

Edge case 1: amount = 0           -> Output: 0    (কিছু না দিয়ে শূন্য)
Edge case 2: coins = [2], amount = 1 -> Output: -1 (বিজোড় বানানো যায় না)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা coin "শেষে বসিয়ে" recurse করা — amount থেকে সেই coin বিয়োগ করে বাকিটা একইভাবে সমাধান করা, সবগুলোর মধ্যে min।

fewest(a):                       # amount a বানাতে min coins
    if a == 0: return 0
    if a < 0:  return INF        # over-shoot, অবৈধ
    return 1 + min( fewest(a - c)  for every coin c )
answer = fewest(amount); INF হলে -1

10. Why brute force is slow

এই recursion exponential — প্রতিটা amount-এ প্রতিটা coin-এর জন্য একটা শাখা, আর একই amount বহু পথ দিয়ে বারবার গোনা হয় (overlapping subproblems)। যেমন fewest(2) বহু জায়গা থেকে আবার আবার ডাকা হয়। amount একটু বড় হলেই tree বিস্ফোরিত হয়।

11. Key observation

মূল observation: distinct amount মাত্র amount + 1-টা (0 থেকে amount)। প্রতিটার min coin একবার গুনে রাখলে, প্রতিটা শুধু কয়েকটা ছোট amount পড়ে — exponential কাজ O(amount × len(coins))-এ নেমে আসে।

12. Optimized intuition

State (শব্দে): dp[a] = ঠিক amount a বানাতে দরকারি minimum coin-সংখ্যা (বানানো অসম্ভব হলে infinity)।

Transition:

dp[a] = 1 + min( dp[a - c]  for every coin c with c <= a )

কারণ: শেষ coin c ধরলে তার আগে amount a - c বানাতে হতো; সব সম্ভব শেষ coin-এর উপর min।

Base case: dp[0] = 0 (শূন্য বানাতে শূন্য coin)। বাকি সব infinity দিয়ে initialize — "এখনো বানানো যায় বলে জানা নেই"।

Answer location: dp[amount]; এখনো infinity থাকলে -1।

Memoization (top-down): উপরের fewest(a) recursion, dict যোগ। Tabulation (bottom-up): a = 1, 2, ..., amount বাঁ-থেকে-ডান ভরো — unbounded বলে প্রতি a-তে সব coin চেষ্টা করি এবং একই array-র ছোট index (a-c) পড়ি, যা এই pass-এই update হয়ে থাকতে পারে (একই coin পুনর্ব্যবহার = বৈধ)।

13. Thinking tweak

মোচড়: "কোন কোন coin-এর কোন combination" — এই বিশাল search না ভেবে শুধু শেষ coin-টা ঠিক করো, বাকিটা একই ছোট problem। এই "last decision" lens-ই DP-র মূল চাবি (state-transition-thinking.md-এর doctrine)। আর মনে রেখো: greedy কেন fail করে — কারণ সে একটা শেষ coin-এ commit করে, DP সব শেষ coin-এর min নেয়।

14. Step-by-step dry run

coins = [1, 2, 5], amount = 11, tabulation (কয়েকটা ধাপ):

1. dp[0] = 0; বাকি সব INF
2. dp[1] = 1 + dp[0] = 1 (coin 1)
3. dp[2] = 1 + min(dp[1], dp[0]) = 1 (coin 2)
4. dp[5] = 1 + min(dp[4], dp[3], dp[0]) = 1 (coin 5)
5. ... এগিয়ে dp[10] = 1 + min(dp[9], dp[8], dp[5]) = 1 + min(3,3,1) = 2 (5+5)
6. dp[11] = 1 + min(dp[10], dp[9], dp[6]) = 1 + min(2,3,2) = 3 (5+5+1)
7. return dp[11] = 3

হাতে মিলিয়ে: 5+5+1 = 3 টা coin। ✔

15. Python solution

INF = float("inf")

# ---- way 1: memoization (top-down, dict = hashing) ----
def coin_change_memo(coins, amount):
    memo = {}
    def fewest(a):                           # amount a বানাতে min coins
        if a == 0:
            return 0
        if a < 0:
            return INF
        if a in memo:
            return memo[a]
        best = INF
        for c in coins:
            sub = fewest(a - c)
            if sub + 1 < best:
                best = sub + 1
        memo[a] = best
        return best
    ans = fewest(amount)
    return ans if ans != INF else -1

# ---- way 2: tabulation (bottom-up) ----
def coin_change_tab(coins, amount):
    dp = [0] + [INF] * amount                # dp[0]=0, বাকি INF
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

# ---- tests ----
cases = [
    ([1, 3, 4], 6, 2),       # greedy fail করে: DP 2, greedy 3
    ([1, 2, 5], 11, 3),
    ([2], 3, -1),
    ([1], 0, 0),
    ([2], 1, -1),
    ([1, 5, 10, 25], 30, 2), # 5 + 25
    ([186, 419, 83, 408], 6249, 20),
]
for coins, amount, want in cases:
    assert coin_change_memo(coins, amount) == want, (coins, amount, coin_change_memo(coins, amount))
    assert coin_change_tab(coins, amount) == want, (coins, amount, coin_change_tab(coins, amount))

print("সব test pass!")

16. Line-by-line code explanation

• coin_change_memo: fewest(a) amount a-র min coins দেয়; a==0 → 0, a<0 → INF; প্রতিটা coin শেষে বসিয়ে দেখে min নেয়; memo (dict) repeated কাজ এড়ায়; INF হলে -1।
• coin_change_tab: dp[0]=0, বাকি INF; a বাঁ-থেকে-ডান ভরে, প্রতিটায় সব coin-এর dp[a-c]+1-এর min; unbounded বলে left-to-right দিক সঠিক।
• শেষে: dp[amount] এখনো INF মানে অসম্ভব, তখন -1।

17. Output walkthrough

cases-এ সাতটা input — তারকা case [1,3,4], 6 -> 2 (greedy 3 দেয়, DP 2), একটা classic 11, দুটো অসম্ভব (-1), amount=0 edge, আর একটা বড় 6249 (memoization stress-test)। প্রতিটার জন্য দুই function-ই মিলতে হবে। সব pass হলে শেষে print: সব test pass!।

18. Time complexity

দুই version-ই O(amount × len(coins)) — প্রতিটা amount-এ প্রতিটা coin একবার চেষ্টা। (Naive recursion ছিল exponential।)

19. Space complexity

• Memoization: O(amount) — dict + recursion stack (গভীরতা amount পর্যন্ত)।
• Tabulation: O(amount) — dp array।

20. Common mistakes

• dp কে 0 দিয়ে initialize করা INF-এর বদলে — তখন "অসম্ভব" আর "শূন্য coin" আলাদা করা যায় না, উত্তর ভুল ছোট আসে।
• শেষে INF check করতে ভুলে যাওয়া — অসম্ভব case-এ -1-এর বদলে বিশাল সংখ্যা ফেরে।
• Greedy দিয়ে solve করার চেষ্টা — [1,3,4], 6 এ ঠিক এই ভুল ধরা পড়ে; coin denomination canonical না হলে greedy ভুল।

21. Which basic problem this inherits from

ভিত্তি: #3 Min Cost Climbing Stairs-এর "ছোট state থেকে min"; এখানে পেছন coin-অনুযায়ী, আর memo-র জন্য hashing (folder 05)। ../state-transition-thinking.md-এর "Problem 3 — Coin Change" section-এ ঠিক এই state, transition, আর greedy কেন fail করে — সব আছে।

22. Similar harder problems

• Minimizing Coins (একই problem, বড় contest limit) — https://cses.fi/problemset/task/1634 (এই tracker-এর #11)
• Coin Combinations I (min নয়, ways গোনো) — https://cses.fi/problemset/task/1635 (#12)
• Perfect Squares (coins = perfect squares) — https://leetcode.com/problems/perfect-squares/

23. Pattern learned

Unbounded knapsack (min): state amount a, transition 1 + min(dp[a-c]) সব coin-এর উপর, base dp[0]=0 বাকি infinity, fill order left-to-right (item পুনর্ব্যবহার বৈধ বলে)। "শেষ item কোনটা?" — এই last-decision lens-ই সব knapsack-এর কঙ্কাল।

24. Final summary

ভবিষ্যতের আমাকে: "Coin Change (min) = unbounded knapsack, amount-এর উপর min।" State dp[a] = amount a-র min coins, transition dp[a] = 1 + min(dp[a-c]), base dp[0]=0 বাকি infinity, উত্তর dp[amount] (INF হলে -1)। মনে রেখো: greedy এখানে ফাঁদ; আর left-to-right fill = unbounded (item বারবার নেওয়া যায়)।

25. JavaScript solution (with test cases)

Unbounded knapsack (min); dp[a] = 1 + min(dp[a-c])। sentinel হিসেবে Infinity, শেষে না বদলালে -1।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[a] = ঠিক amount a বানাতে min coins; Infinity = এখনো অজানা
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;                                  // শূন্য বানাতে শূন্য coin
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && dp[a - c] + 1 < dp[a]) {  // c শেষে বসিয়ে দেখি
        dp[a] = dp[a - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];   // অসম্ভব হলে -1
}
// ---- test cases (example + edge) ----
const cases = [
  [[1, 3, 4], 6, 2],                          // greedy fail করে: DP 2
  [[1, 2, 5], 11, 3],
  [[2], 3, -1],                               // অসম্ভব
  [[1], 0, 0],                                // amount 0 edge
  [[2], 1, -1],
  [[1, 5, 10, 25], 30, 2],
  [[186, 419, 83, 408], 6249, 20],
];
for (const [coins, amount, want] of cases) {
  assert(coinChange(coins, amount) === want, "coin " + amount);
}
console.log("সব JS test pass!");

JS টীকা: sentinel হিসেবে Infinity ব্যবহার করো (Python-এর float("inf"))-এর মতো — dp[a-c] + 1 Infinity হলেও সংখ্যাই থাকে (Infinity + 1 = Infinity), তাই compare নিরাপদ; শেষে === Infinity দিয়ে "অসম্ভব" ধরে -1। new Array(n).fill(Infinity) primitive বলে নিরাপদ; dp[0] = 0 base ভুলে গেলে সব Infinity হয়ে ভুল উত্তর আসত।

26. TypeScript solution (with test cases)

function coinChange(coins: number[], amount: number): number {
  const dp: number[] = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && dp[a - c] + 1 < dp[a]) {
        dp[a] = dp[a - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number[], number, number]> = [
  [[1, 3, 4], 6, 2],
  [[1, 2, 5], 11, 3],
  [[2], 3, -1],
  [[1], 0, 0],
  [[2], 1, -1],
  [[1, 5, 10, 25], 30, 2],
];
for (const [coins, amount, want] of cases) expect(coinChange(coins, amount), want, "coin");
console.log("সব TS test pass!");

TS টীকা: coins: number[] ও return number typing করায় ফাংশন-চুক্তি স্পষ্ট; dp: number[] রাখায় Infinity (যা JS-এ number) মিশলেও type-safe থাকে। cases: Array<[number[], number, number]> tuple-type প্রতিটা case-এর [coins, amount, expected] গঠন locked করে।

27. কোথায় কাজে লাগে (real-world use)

• Currency / change-making: ন্যূনতম সংখ্যক কয়েন/নোটে নির্দিষ্ট অঙ্ক ভাঙা (ATM, vending machine dispenser)।
• Minimum units to reach target: সীমাহীন supply-র কিছু denomination দিয়ে ঠিক target বানাতে ন্যূনতম unit।
• Resource packing (unbounded): নির্দিষ্ট মাপের module বারবার ব্যবহার করে ঠিক capacity পূরণ, ন্যূনতম সংখ্যায়।
• Tiling / cutting stock (1D): নির্দিষ্ট দৈর্ঘ্যের টুকরো দিয়ে length পূরণে ন্যূনতম টুকরো।
• Step / move minimization: নির্দিষ্ট কিছু move-size দিয়ে ঠিক দূরত্বে পৌঁছাতে ন্যূনতম move (greedy কেন fail করে তার ক্লাসিক উদাহরণ)।

মূল pattern: "শেষ item কোনটা?" — last-decision lens; dp[a] = 1 + min(dp[a-c]), left-to-right fill = item পুনর্ব্যবহারযোগ্য (unbounded)।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।