Problem link ও উৎস
- **Original source:** Classic unbounded-knapsack minimization exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** Unbounded knapsack (min)
- **Basic idea inherited from:** #3 Min Cost Climbing Stairs — কিন্তু একটা amount-এর উপর min, আর memo-র জন্য hashing
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো coin-এর মান দেওয়া (`coins`), প্রত্যেকটার supply **অসীম** — যত খুশি ব্যবহার করতে পারো। আর একটা target `amount` দেওয়া। সবচেয়ে **কম** কয়টা coin দিয়ে ঠিক `amount`-টা বানানো যায় বের করো। কোনোভাবেই না বানানো গেলে `-1` return করো।
```text
coins = [1, 3, 4], amount = 6
greedy (সবচেয়ে বড় আগে): 4 + 1 + 1 = 3 টা coin
সঠিক DP উত্তর : 3 + 3 = 2 টা coin <- greedy fail করে!
```
### Input ও output {#8-example-input-and-output}
```text
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 (বিজোড় বানানো যায় না)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দোকানে ঠিক `amount` টাকা দিতে হবে, পকেটে অসীম সংখ্যক কিছু নির্দিষ্ট মানের কয়েন। তুমি চাও যত কম কয়েন গুনতে হয়। প্রতিটা সম্ভাব্য "শেষ কয়েন"-এর জন্য ভাবো: "এই কয়েনটা শেষে দিলে বাকি টাকাটা সবচেয়ে কম কয়েনে কীভাবে দিতাম?" — তারপর সব বিকল্পের মধ্যে সবচেয়ে কম-কয়েনের রাস্তাটা বেছে নাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 লাগে না, এক মাত্রাই যথেষ্ট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা coin "শেষে বসিয়ে" recurse করা — amount থেকে সেই coin বিয়োগ করে বাকিটা একইভাবে সমাধান করা, সবগুলোর মধ্যে min।
```text
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:**
```text
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 নেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[a]` = amount `a`-র জন্য min coins। `coins = [1, 3, 4]`, `amount = 6`:
```text
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-এ ধাপে ধাপে {#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। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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`।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-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 {#26-typescript-solution-with-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