Problem link ও উৎস
- **Original source:** CSES Problem Set — Dynamic Programming section
- **Platform:** CSES —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** Unbounded knapsack (min)
- **Basic idea inherited from:** #10 Coin Change — হুবহু একই recurrence, শুধু বড় contest limit আর `-1` convention
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n`-টা coin-এর মান দেওয়া, প্রত্যেকটার supply **অসীম**, আর একটা target sum `x`। সবচেয়ে **কম** কয়টা coin দিয়ে ঠিক `x` বানানো যায় বের করো। বানানো অসম্ভব হলে `-1`। এটা #10 Coin Change-এর contest সংস্করণ — same problem, কিন্তু judge-এ বড় limit (target `10^6` পর্যন্ত), তাই efficient tabulation দরকার।
```text
coins = [1, 5, 7], x = 11
সবচেয়ে কম: 5 + 5 + 1 = 3 টা coin
(7 + 1 + 1 + 1 + 1 = 5 টা — খারাপ)
```
### Input ও output {#8-example-input-and-output}
```text
Input : coins = [1,5,7], x = 11 -> Output: 3 (5+5+1)
Input : coins = [2,3,5], x = 9 -> Output: 3 (5+2+2 বা 3+3+3)
Input : coins = [2,4,6], x = 10 -> Output: 2 (4+6)
Edge case 1: x = 0 -> Output: 0 (কিছু না দিয়ে শূন্য)
Edge case 2: coins = [3], x = 7 -> Output: -1 (3-এর গুণিতক নয়)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো cashier-এর কাছে নির্দিষ্ট কিছু মানের অসীম কয়েন, আর তাকে ঠিক `x` টাকা ফেরত দিতে হবে যত কম কয়েনে সম্ভব। প্রতিটা সম্ভাব্য "শেষ কয়েন"-এর জন্য সে ভাবে: "এটা শেষে দিলে বাকি টাকা সবচেয়ে কম কয়েনে কত লাগত?" — তারপর সব বিকল্পের মধ্যে সবচেয়ে অল্প-কয়েনের রাস্তা বেছে নেয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি সরাসরি #10 Coin Change (min)। recurrence অক্ষরে অক্ষরে এক: `dp[x] = 1 + min(dp[x-c])`। তফাত শুধু প্রেক্ষাপট — CSES-এ input বড়, তাই recursion-এর বদলে iterative tabulation নিরাপদ (stack overflow এড়াতে), আর "impossible"-কে `-1` দিয়ে report করতে হয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একই last-decision প্রশ্ন: **শেষে কোন coin বসালাম?** শেষ coin `c` হলে তার আগে sum `x - c` বানাতে হয়েছিল; সেটার min coin-সংখ্যা + 1। সব সম্ভব শেষ coin-এর উপর `min` নিলে globally minimum। Greedy এখানেও সাধারণভাবে ভুল — DP সব শেষ coin-এর history দেখে বলেই ঠিক।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **1D array** `dp` (size `x + 1`), `dp[s]` = ঠিক sum `s` বানাতে minimum coin-সংখ্যা (অসম্ভব হলে infinity)। বড় limit-এর জন্য iterative array-ই উপযুক্ত (top-down recursion CSES-এ stack-এ আটকাতে পারে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State একটামাত্র সংখ্যা: কত sum বানাতে বাকি। sum-কে index ধরা flat array নিখুঁত — `dp[s]` ঠিক sum `s`-এর উত্তর ধরে। Unbounded supply মানে coin পুনর্ব্যবহার বৈধ, তাই transition একই array-র ছোট index (`s-c`) পড়ে, এক মাত্রাই যথেষ্ট। iterative হওয়ায় বড় `x`-এও recursion-limit সমস্যা নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা coin "শেষে বসিয়ে" recurse করা — sum থেকে সেই coin বিয়োগ করে বাকিটা একইভাবে সমাধান, সবগুলোর মধ্যে min।
```text
solve(s): # sum s বানাতে min coins
if s == 0: return 0
if s < 0: return INF
return 1 + min( solve(s - c) for every coin c )
answer = solve(x); INF হলে -1
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **exponential** — প্রতিটা sum-এ প্রতিটা coin একটা শাখা খোলে, আর একই sum বহু পথ দিয়ে বারবার গোনা হয় (overlapping subproblems)। CSES-এর বড় `x`-এ (10^6 পর্যন্ত) এটা সম্পূর্ণ অসম্ভব — exponential তো বটেই, recursion-ও এত গভীরে যাবে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct sum মাত্র `x + 1`-টা** (0 থেকে `x`)। প্রতিটার min coin একবার iterative-ভাবে গুনে রাখলে পুরোটা O(x × n)-এ হয়ে যায় — CSES limit-এর জন্য যথেষ্ট দ্রুত, আর recursion stack-এর ঝুঁকিও নেই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[s]` = ঠিক sum `s` বানাতে দরকারি minimum coin-সংখ্যা (অসম্ভব হলে infinity)।
**Transition:**
```text
dp[s] = 1 + min( dp[s - c] for every coin c with c <= s )
```
কারণ: শেষ coin `c` ধরলে তার আগে sum `s - c` বানাতে হতো; সব সম্ভব শেষ coin-এর উপর min।
**Base case:** `dp[0] = 0`। বাকি সব infinity — "এখনো বানানো যায় বলে জানা নেই"।
**Answer location:** `dp[x]`; infinity থাকলে `-1`।
Tabulation (bottom-up, CSES-এ প্রধান উপায়): `s = 1, 2, ..., x` বাঁ-থেকে-ডান ভরো — unbounded বলে এই দিকই সঠিক (একই coin আবার নেওয়া বৈধ)। Memoization (top-down): একই recurrence, dict; ছোট input-এ ঠিক আছে, কিন্তু বড় `x`-এ recursion-limit বাড়াতে হতে পারে — তাই contest-এ tabulation default।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** #10-এর সাথে এটা **একই** problem — নতুন কিছু শেখার নেই, শুধু **scale**-এর শিক্ষা: একই DP কখন iterative করতে হয়। recursion সুন্দর কিন্তু 10^6 গভীর state-এ stack ভেঙে যায়; তাই contest-এ আগে tabulation ভাবো। "একই tool, বড় ডেটা = bottom-up" — এই reflex-টাই এখানকার নতুন জিনিস।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[s]` = sum `s`-এর min coins। `coins = [1, 5, 7]`, `x = 11`:
```text
s : 0 1 2 3 4 5 6 7 8 9 10 11
dp[s]: 0 1 2 3 4 1 2 1 2 3 2 3
dp[s] = 1 + min( dp[s - c] for each coin c <= s )
dp[0] = 0 (base)
dp[1..4] = 1,2,3,4 (শুধু 1 দিয়ে)
dp[5] = 1 + min(dp[4], dp[0]) = 1 (coin 5)
dp[7] = 1 + min(dp[6], dp[2], dp[0]) = 1 (coin 7)
dp[10] = 1 + min(dp[9], dp[5], dp[3]) = 1 + min(3,1,3) = 2 (5+5)
dp[11] = 1 + min(dp[10], dp[6], dp[4]) = 1 + min(2,2,4) = 3 <- answer (5+5+1)
```
প্রতিটা sum-এ সব coin "শেষে" বসিয়ে দেখি; ছোট subproblem-এর min + 1। উত্তর `dp[11] = 3`।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`coins = [2, 4, 6]`, `x = 10`, tabulation:
1. `dp[0] = 0`; বাকি INF
2. `dp[2] = 1 + dp[0] = 1` (coin 2)
3. `dp[4] = 1 + min(dp[2], dp[0]) = 1` (coin 4)
4. `dp[6] = 1 + min(dp[4], dp[2], dp[0]) = 1` (coin 6)
5. `dp[8] = 1 + min(dp[6], dp[4], dp[2]) = 1 + 1 = 2` (4+4 বা 6+2)
6. `dp[10] = 1 + min(dp[8], dp[6], dp[4]) = 1 + min(2,1,1) = 2` (4+6)
7. return `dp[10] = 2`
হাতে মিলিয়ে: 4 + 6 = 2 টা coin। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
INF = float("inf")
# ---- way 1: tabulation (bottom-up) — CSES-এর প্রধান উপায় ----
def minimizing_coins_tab(coins, target):
dp = [0] + [INF] * target # dp[0]=0, বাকি INF
for s in range(1, target + 1):
for c in coins:
if c <= s and dp[s - c] + 1 < dp[s]:
dp[s] = dp[s - c] + 1
return dp[target] if dp[target] != INF else -1
# ---- way 2: memoization (top-down) — ছোট input-এ ----
def minimizing_coins_memo(coins, target):
memo = {0: 0}
def solve(s): # sum s বানাতে min coins
if s < 0:
return INF
if s in memo:
return memo[s]
best = INF
for c in coins:
sub = solve(s - c) + 1
if sub < best:
best = sub
memo[s] = best
return best
ans = solve(target)
return ans if ans != INF else -1
# ---- tests ----
cases = [
([1, 5, 7], 11, 3), # CSES sample: 5+5+1
([2, 3, 5], 9, 3), # 5+2+2 বা 3+3+3
([2, 4, 6], 10, 2), # 4+6
([1], 0, 0),
([3], 7, -1), # 3-এর গুণিতক নয়
([1, 2, 5], 11, 3), # 5+5+1
]
for coins, target, want in cases:
assert minimizing_coins_tab(coins, target) == want, (coins, target, minimizing_coins_tab(coins, target))
assert minimizing_coins_memo(coins, target) == want, (coins, target, minimizing_coins_memo(coins, target))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `minimizing_coins_tab`: `dp[0]=0`, বাকি INF; `s` বাঁ-থেকে-ডান ভরে, প্রতিটায় সব coin-এর `dp[s-c]+1`-এর min; unbounded বলে left-to-right সঠিক; শেষে INF হলে `-1`।
- `minimizing_coins_memo`: `solve(s)` sum `s`-এর min coins দেয়; `s<0` → INF; প্রতিটা coin শেষে বসিয়ে min; `memo` (dict) repeated কাজ এড়ায়।
- দুই function-ই অসম্ভব sum-এ INF ধরে রাখে, শেষে `-1` দেয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ ছয়টা input — CSES sample `[1,5,7], 11 -> 3`, একটা `9` (দুই রকম optimal), একটা `2`-coin solution, `x=0` edge, একটা impossible (`-1`), আর আরেকটা classic। প্রতিটার জন্য দুই function-ই মিলতে হবে। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
দুই version-ই **O(x × n)** — প্রতিটা sum-এ প্রতিটা coin একবার (`n` = coin-সংখ্যা)। CSES limit-এর জন্য যথেষ্ট দ্রুত।
### অতিরিক্ত জায়গা {#19-space-complexity}
- Tabulation: **O(x)** — `dp` array।
- Memoization: **O(x)** — dict + recursion stack (বড় `x`-এ এই stack-ই ঝুঁকি, তাই tabulation default)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- বড় `x`-এ recursion ব্যবহার করে stack overflow খাওয়া — CSES-এ tabulation দিয়ে শুরু করো।
- `dp` কে 0 দিয়ে initialize (INF-এর বদলে) — তখন "অসম্ভব" আর "শূন্য" আলাদা হয় না।
- শেষে INF check ভুলে যাওয়া — impossible case-এ `-1`-এর বদলে বিশাল সংখ্যা ছাপে; CSES তখন Wrong Answer দেবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #10 Coin Change (min)-এর হুবহু recurrence; নতুনত্ব শুধু scale (iterative tabulation) আর `-1` convention। [../state-transition-thinking.md](../state-transition-thinking.md)-এর "Problem 3 — Coin Change" section-ই এর তত্ত্ব; [../patterns.md](../patterns.md)-এর "Unbounded knapsack" family-ও এখানে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Coin Change (LeetCode সংস্করণ, একই recurrence) —