কনটেন্টে যান

016 — Coin Change

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

Problem link ও উৎস

  • Original source: Classic cross-topic capstone interview problem (unbounded knapsack family)
  • Platform: LeetCode — https://leetcode.com/problems/coin-change/
  • Topic: dynamic programming + recursion
  • Difficulty: Medium
  • Pattern: Unbounded knapsack DP (minimize count, coins reusable)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 12 dynamic programming (প্রতিটা amount-এর জন্য একটা sub-answer রাখা) আর 06 recursion (memo form — "এই amount বানাতে কম coin?" প্রশ্নটাকে ছোট amount-এর উপর recurse করানো)। দুই tool জোড়া লাগলেই unbounded knapsack।

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

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

তোমাকে কিছু coin-এর denomination দেওয়া আছে (যেমন [1, 2, 5]) আর একটা target amount। তোমার কাজ: সবচেয়ে কম সংখ্যক coin দিয়ে ঠিক ওই amount বানাও। প্রতিটা coin যতবার খুশি ব্যবহার করা যায়। যদি কোনোভাবেই amount-টা বানানো না যায়, return করো -1।

উদাহরণ
coins : [1, 2, 5],  amount : 11
সেরা : 5 + 5 + 1  -> 3টা coin

Input ও output

উদাহরণ
Input : coins = [1, 2, 5], amount = 11   -> Output: 3    # 5 + 5 + 1
Input : coins = [2], amount = 3          -> Output: -1   # বানানো অসম্ভব
Input : coins = [1], amount = 0          -> Output: 0    # কিছু লাগে না

Edge case 1 (একটাই coin, মেলে না): coins = [2], amount = 1  -> Output: -1
Edge case 2 (greedy ফাঁদ): coins = [1, 3, 4], amount = 6   -> Output: 2  # 3+3, greedy দিত 4+1+1=3

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

ভাবো দোকানে খুচরো ফেরত দিচ্ছ আর তোমার পকেটে অসীম সংখ্যক ৳1, ৳2, ৳5 কয়েন আছে। তুমি যত কম কয়েন দিয়ে হিসাব মেলাতে পারো, গোনা তত সহজ, পকেটও তত হালকা। প্রতিটা সম্ভাব্য মোট টাকার জন্য তুমি আগেই মুখস্থ করে রাখছ "এটা মেলাতে ন্যূনতম কত কয়েন" — পরে বড় অঙ্ক এলে শুধু একটা কয়েন বসিয়ে বাকিটার মুখস্থ উত্তর তুলে নাও।

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

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

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 12 dynamic programming থেকে: প্রতিটা ছোট amount-এর জন্য "এটা বানাতে কমপক্ষে কত coin" — একটা sub-answer রাখা, আর বড় amount-এর উত্তর ছোটগুলোর উপর দাঁড় করানো।
  • 06 recursion থেকে: মূল প্রশ্ন solve(amount) কে ভাঙা — "একটা coin c নাও, বাকিটা solve(amount - c)" — এই recursive সংজ্ঞাটাই memo বসালে DP।

একা recursion তোমাকে দেয় প্রশ্ন ছোট করার ক্ষমতা; একা DP দেয় একই sub-answer বারবার হিসাব না করে reuse করার ক্ষমতা। দুটো মিললে O(amount × coins)।

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

লুকানো logic একটা optimal substructure: amount বানানোর সেরা উপায় = কোনো একটা coin c (যেখানে c <= amount) শেষে রাখা, আর তার আগে amount - c বানানোর সেরা উপায়। তাই —

উদাহরণ
dp[a] = 1 + min( dp[a - c] )   সব coin c-এর উপর, যেখানে c <= a

মানে: প্রতিটা amount a-র জন্য সব coin try করো, প্রতিটা dp[a-c]-র সাথে 1 যোগ করো (এই coin-টা গুনে), সবচেয়ে ছোটটা নাও। dp[0] = 0 (শূন্য amount বানাতে কোনো coin লাগে না)।

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

একটা 1D array dp লাগে, length amount + 1। dp[a] ধরে রাখে "a বানাতে কমপক্ষে কত coin"। এটাই 12 DP-র bottom-up table; 06 recursion-এর memo cache-ও ঠিক একই জিনিস, শুধু উল্টোদিক থেকে ভরা।

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

আমাদের প্রতিটা amount-এর উত্তর বারবার দরকার হয় (dp[11]-এর জন্য dp[6] লাগে, dp[6]-এর জন্য dp[1]...), আর একই sub-amount অনেক পথে ফিরে আসে। তাই প্রতিটা amount-এর উত্তর একবার হিসাব করে একটা index-able array-তে রেখে দিলে (06 recursion-এর memoization, 12 DP-র table) আর কখনো নতুন করে গুনতে হয় না। amount-গুলো 0..amount পর্যন্ত ছোট ও পরপর integer, তাই array-ই নিখুঁত — O(1) index।

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

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

প্রথম সরল চিন্তা: একটা recursion — solve(a) মানে "a বানাতে কম coin"। প্রতিটা coin try করো, বাকিটা recurse করো, সবচেয়ে কমটা নাও।

উদাহরণ
def solve(a):
    if a == 0: return 0
    if a < 0:  return INF
    return 1 + min(solve(a - c) for c in coins)

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

memo ছাড়া এই recursion একই sub-amount বারবার নতুন করে হিসাব করে — call tree exponential, প্রায় O(coins^amount)। যেমন dp[6]-এর জন্য dp[1] অনেক আলাদা পথে গণনা হয়। এই পুনরাবৃত্তিই 12 DP দূর করতে আসে — প্রতিটা amount একবার গুনে cache করে।

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

মূল observation: amount বানানোর সেরা উপায় ঠিক একটা "শেষ coin"-এর পছন্দে ভেঙে যায় — শেষ coin c হলে বাকি problem হলো amount - c বানানো, যেটা একই ধরনের ছোট problem। আর amount - c-র সেরা উত্তর কোন বড় amount চাইছে তার উপর নির্ভর করে না — তাই একবার গুনে রাখলেই চলে। এই observation greedy-র ফাঁদ এড়ায় (বড় coin আগে নেওয়া সবসময় সেরা নয়)।

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

amount পর্যন্ত একটা table নাও, dp[0] = 0, বাকি সব INF। a = 1 থেকে amount পর্যন্ত হাঁটো; প্রতিটা a-তে সব coin try করো — c <= a হলে dp[a]-কে dp[a-c] + 1-এর সাথে তুলনা করে ছোটটা রাখো। শেষে dp[amount] যদি এখনো INF থাকে, মানে অসম্ভব — return -1; নাহলে সেটাই উত্তর। প্রতিটা amount একবার, প্রতিটায় সব coin — O(amount × coins)।

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

মোচড়: "কোন coin আগে নেব?" (greedy) ভাবার বদলে ভাবো "শেষ coin-টা কী হবে?" — এই একটা প্রশ্ন বড় problem-টাকে একটা ছোট dp[a-c]-তে নামিয়ে দেয়, আর সব শেষ-coin try করে সেরাটা নিলে greedy-র ভুল আর হয় না।

ছবিতে বোঝা

coins = [1, 2, 5], amount = 6 — dp array ভরা হচ্ছে (INF = এখনো অজানা/অসম্ভব):

উদাহরণ
a:    0   1   2   3   4   5   6
      --- --- --- --- --- --- ---
init  0  INF INF INF INF INF INF

a=1: min via 1 -> dp[0]+1 = 1                      dp[1]=1
a=2: via 1 -> dp[1]+1=2 ; via 2 -> dp[0]+1=1       dp[2]=1
a=3: via 1 -> dp[2]+1=2 ; via 2 -> dp[1]+1=2       dp[3]=2
a=4: via 1 -> dp[3]+1=3 ; via 2 -> dp[2]+1=2       dp[4]=2
a=5: via 1 ->3 ; via 2 ->dp[3]+1=3 ; via 5 ->dp[0]+1=1  dp[5]=1
a=6: via 1 ->dp[5]+1=2 ; via 2 ->dp[4]+1=3 ; via 5 ->dp[1]+1=2  dp[6]=2

dp = [0, 1, 1, 2, 2, 1, 2]      উত্তর dp[6] = 2  (5 + 1)

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

coins = [1, 2, 5], amount = 3:

  1. শুরু: dp = [0, INF, INF, INF]
  2. a=1: coin 1 → dp[0]+1 = 1; coin 2,5 বড় → skip; dp[1] = 1
  3. a=2: coin 1 → dp[1]+1 = 2; coin 2 → dp[0]+1 = 1; dp[2] = 1
  4. a=3: coin 1 → dp[2]+1 = 2; coin 2 → dp[1]+1 = 2; coin 5 বড় → skip; dp[3] = 2
  5. dp[3] = 2 != INF → return 2 (যেমন 1 + 2)

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

Python

Python
def coin_change(coins, amount):
    INF = amount + 1                 # যেকোনো বৈধ উত্তরের চেয়ে বড় sentinel
    dp = [0] + [INF] * amount        # dp[0]=0, বাকি সব "অজানা"
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:               # এই coin বসানো যায়
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

# ---- tests ----
assert coin_change([1, 2, 5], 11) == 3        # 5+5+1
assert coin_change([2], 3) == -1              # অসম্ভব
assert coin_change([1], 0) == 0               # কিছু লাগে না
assert coin_change([1], 2) == 2               # 1+1
assert coin_change([2, 5, 10, 1], 27) == 4    # 10+10+5+2
assert coin_change([1, 3, 4], 6) == 2         # 3+3, greedy ফাঁদ
print("সব test pass!")

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

  • INF = amount + 1 — coin একটাও 0 মূল্যের নয়, তাই বৈধ উত্তর কখনো amount-এর বেশি coin চায় না; amount + 1 নিরাপদ "অসম্ভব" চিহ্ন।
  • dp = [0] + [INF] * amount — dp[0] = 0 (শূন্য বানাতে শূন্য coin), বাকি সব এখনো অজানা।
  • for a in range(1, amount + 1) — ছোট থেকে বড় amount, যাতে dp[a-c] আগেই গণনা হয়ে থাকে (12 DP-র fill order)।
  • for c in coins — প্রতিটা সম্ভাব্য "শেষ coin" try করা (06 recursion-এর branching)।
  • if c <= a — coin amount-এর চেয়ে বড় হলে বসানো যায় না, skip।
  • dp[a] = min(dp[a], dp[a - c] + 1) — এই coin গুনে (+1) আগের best-এর সাথে তুলনা।
  • return dp[amount] if dp[amount] != INF else -1 — এখনো INF থাকলে কোনো combination মেলেনি → -1।

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

coins=[1,2,5], amount=11-এ table ভরতে ভরতে dp[11] শেষে min-এর মাধ্যমে dp[6]+1 = 3 (coin 5 বসিয়ে) পায় — অর্থাৎ 5+5+1, return 3, assert pass। coins=[2], amount=3-এ কোনো coin দিয়েই odd amount মেলে না, dp[3] INF-ই থাকে → return -1। greedy-ফাঁদ [1,3,4], amount=6-এ DP 3+3 = 2 বের করে (greedy ভুল করে 3 দিত)। শেষে print: সব test pass!।

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

সময়

O(amount × coins) — প্রতিটা amount 1..amount-এর জন্য একবার, ভেতরে সব coin (len(coins)-টা) try করা।

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

O(amount) — একটা মাত্র 1D dp array, length amount + 1। 06 recursion-এ করলে call-stack O(amount) লাগত; bottom-up table সেটাও বাঁচায়।

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

  • greedy দিয়ে সমাধান করা (সবসময় বড় coin আগে) — [1,3,4], amount=6-এর মতো case-এ ভুল (greedy 3, সঠিক 2)।
  • INF-কে এমন বড় রাখা যে dp[a-c] + 1 overflow/ভুল হয় — amount + 1 রাখলে +1 করেও বৈধ উত্তরের চেয়ে বড়ই থাকে, ঝামেলা নেই।
  • dp[0] সেট না করা — base না দিলে কোনো amount-ই বানানো যাবে না।
  • শেষে INF-চেক ভুলে যাওয়া — তখন অসম্ভব case-এ amount + 1-এর মতো ভুল বড় সংখ্যা return হয়, -1 না।

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

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

ভিত্তি: প্রতিটা sub-amount-এর জন্য sub-answer রাখা (12 DP-র ../../12-dynamic-programming/patterns.md, knapsack family) + মূল প্রশ্নকে ছোট amount-এ recurse করানো (06 recursion-এর ../../06-recursion-and-backtracking/, memoization)। এই দুটো cold অবস্থায় জানা থাকলে unbounded knapsack নিজে থেকেই বেরিয়ে আসে।

পরের অনুশীলন

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

Unbounded knapsack / min-coins DP: প্রতিটা target-এর সেরা উত্তরকে "একটা শেষ item বেছে, বাকিটার আগের উত্তর তোলা" দিয়ে ভেঙে O(target × items)-এ পৌঁছানো। item পুনর্ব্যবহারযোগ্য বলে inner loop প্রতিবার সব item দেখে। DP + recursion(memo) combo-র canonical রূপ।

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

ভবিষ্যতের আমাকে: "minimum number of items to reach a target, items reusable" দেখলেই unbounded knapsack DP মনে করবে — dp[a] = min over c of dp[a-c] + 1, dp[0]=0, INF দিয়ে "অসম্ভব" ধরো। greedy-তে যেয়ো না (coin denomination অদ্ভুত হলে ভুল হয়)। শেষে INF-চেক করে -1 ফেরত দিতে ভুলো না। DP table আর memoized recursion-এর সবচেয়ে পরিষ্কার মেলবন্ধন।

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