কনটেন্টে যান

010 — Coin Change

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

কতগুলো 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 করে!

Input ও 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 (বিজোড় বানানো যায় না)

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা 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

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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 পুনর্ব্যবহার = বৈধ)।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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।

ছোট input-এ ধাপে ধাপে

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। ✔

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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।

Output মিলিয়ে দেখা

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!।

JavaScript ও test cases

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

JavaScript
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 হয়ে ভুল উত্তর আসত।

TypeScript ও test cases

TypeScript
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 করে।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: #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 করে — সব আছে।

পরের অনুশীলন

কৌশলটি মনে রাখুন

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-এর কঙ্কাল।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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 বারবার নেওয়া যায়)।

কোথায় কাজে লাগে

  • 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।