Problem link ও উৎস
- **Original source:** Classic cross-topic capstone interview problem (unbounded knapsack family)
- **Platform:** LeetCode —
- **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।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে কিছু coin-এর denomination দেওয়া আছে (যেমন `[1, 2, 5]`) আর একটা target `amount`। তোমার কাজ: **সবচেয়ে কম সংখ্যক coin** দিয়ে ঠিক ওই amount বানাও। প্রতিটা coin **যতবার খুশি** ব্যবহার করা যায়। যদি কোনোভাবেই amount-টা বানানো না যায়, return করো -1।
```text
coins : [1, 2, 5], amount : 11
সেরা : 5 + 5 + 1 -> 3টা coin
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দোকানে খুচরো ফেরত দিচ্ছ আর তোমার পকেটে অসীম সংখ্যক ৳1, ৳2, ৳5 কয়েন আছে। তুমি যত কম কয়েন দিয়ে হিসাব মেলাতে পারো, গোনা তত সহজ, পকেটও তত হালকা। প্রতিটা সম্ভাব্য মোট টাকার জন্য তুমি আগেই মুখস্থ করে রাখছ "এটা মেলাতে ন্যূনতম কত কয়েন" — পরে বড় অঙ্ক এলে শুধু একটা কয়েন বসিয়ে বাকিটার মুখস্থ উত্তর তুলে নাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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` বানানোর সেরা উপায়। তাই —
```text
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।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: একটা recursion — `solve(a)` মানে "`a` বানাতে কম coin"। প্রতিটা coin try করো, বাকিটা recurse করো, সবচেয়ে কমটা নাও।
```text
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-র ভুল আর হয় না।
### ছবিতে বোঝা {#7-visual-explanation}
`coins = [1, 2, 5]`, `amount = 6` — `dp` array ভরা হচ্ছে (`INF` = এখনো অজানা/অসম্ভব):
```text
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-এ ধাপে ধাপে {#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`)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 না।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: প্রতিটা sub-amount-এর জন্য sub-answer রাখা (12 DP-র [../../12-dynamic-programming/patterns.md](../../12-dynamic-programming/patterns.md), knapsack family) + মূল প্রশ্নকে ছোট amount-এ recurse করানো (06 recursion-এর [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md), memoization)। এই দুটো cold অবস্থায় জানা থাকলে unbounded knapsack নিজে থেকেই বেরিয়ে আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Coin Change II (এখানে combination **গোনা**, minimize না — order matters না, তাই loop order উল্টো) —