Skip to content

016 — Coin Change

Source

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

1. Problem in simple words

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

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

2. Which basic idea does this inherit from?

এই 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)।

3. What is the hidden math or logic?

লুকানো 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 লাগে না)।

4. Which data structure is needed?

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

5. Why this data structure fits

আমাদের প্রতিটা 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।

6. Real-life analogy

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

7. Visual explanation

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)

8. Example input and 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

9. Brute force thinking

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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)

15. Python solution

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

16. Line-by-line code explanation

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

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

ভিত্তি: প্রতিটা 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 নিজে থেকেই বেরিয়ে আসে।

22. Similar harder problems

23. Pattern learned

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

24. Final summary

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