Problem link ও উৎস
- **Original source:** CSES Problem Set — Dynamic Programming section
- **Platform:** CSES —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** Unbounded counting
- **Basic idea inherited from:** #4 Dice Combinations (ordered counting) আর #10 Coin Change (unbounded coin loop)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n`-টা coin-এর মান দেওয়া, প্রত্যেকটার supply **অসীম**, আর একটা target sum `x`। ঠিক `x` বানানোর কতগুলো **ordered** উপায় (coin sequence) আছে গোনো — মানে `[2, 3]` আর `[3, 2]` আলাদা গোনা হয়। উত্তর বড় হতে পারে, তাই `10^9 + 7` দিয়ে modulo নাও। এটা #10-এর "ways গোনো" সংস্করণ — "সবচেয়ে কম coin" নয়, "কত রকমে"।
```text
coins = [2, 3, 5], x = 9
ordered ways = 8
যেমন: 2+2+5, 2+5+2, 5+2+2, 3+3+3, 2+2+2+3, 2+2+3+2, 2+3+2+2, 3+2+2+2
```
### Input ও output {#8-example-input-and-output}
```text
Input : coins = [2,3,5], x = 9 -> Output: 8 (ordered)
Input : coins = [1,2], x = 4 -> Output: 5 (Fibonacci-মতো)
Input : coins = [3], x = 9 -> Output: 1 (শুধু 3+3+3)
Edge case 1: x = 0 -> Output: 1 (একটাই: খালি sequence)
Edge case 2: coins = [3], x = 7 -> Output: 0 (3-এর গুণিতক নয়)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি ঠিক `x` মূল্যের টোকেন একটার পর একটা ফেলে একটা stack বানাচ্ছ, প্রতিটা টোকেন নির্দিষ্ট কিছু মানের একটা। দুটো stack আলাদা যদি কোনো position-এ টোকেনের মান আলাদা হয় (order matters)। মোট কত রকম stack `x`-এ শেষ হয়? প্রতিটা সম্ভাব্য **সবার উপরের** টোকেনের জন্য ভাবো — সেটা সরালে নিচে একটা ছোট valid stack (sum `x - c`); সব শীর্ষ-টোকেনের ways যোগ করো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত্তি একসাথে। #4 Dice Combinations-এর **ordered counting** চিন্তা (sequence-এর শেষ ধাপ কী?) আর #10 Coin Change-এর **unbounded coin loop** (প্রতিটা coin বারবার নেওয়া যায়)। Dice-এ "শেষ roll" 1–6 ছিল; এখানে "শেষ coin" `coins`-এর যেকোনোটা। মূল মন্ত্র এক: শেষ ধাপের উপর ভাগ করে ছোট subproblem-এর ways যোগ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা sum `x`-এর ordered sequence-এর **শেষ coin** কী, তার উপর ভাগ করো। শেষ coin `c` হলে তার আগের অংশ একটা ordered sequence যার sum `x - c`। শেষ coin-এর প্রতিটা পছন্দ disjoint দল তৈরি করে (কারণ শেষ element আলাদা), আর সব sequence cover করে। তাই `ways(x) = Σ ways(x - c)` সব coin `c`-র উপর। Order গোনা হয় কারণ একই multiset-এর প্রতিটা ভিন্ন শেষ-element আলাদা পথ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **1D array** `dp` (size `x + 1`), `dp[s]` = sum `s` বানানোর ordered sequence-সংখ্যা (mod `10^9+7`)। Top-down করলে একটা **dict/cache** (sum → count)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State একটামাত্র সংখ্যা: কত sum বানাতে হবে। sum-কে index ধরা flat array নিখুঁত — `dp[s]` ঠিক sum `s`-এর ways ধরে। ordered গোনা বলে loop-এ **sum বাইরে, coin ভেতরে** — প্রতিটা sum-এ সব coin "শেষে" বসাই, যাতে একই multiset-এর প্রতিটা ordering আলাদা গোনা হয়। এক মাত্রাই যথেষ্ট, কারণ history লাগে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা coin "শেষে বসিয়ে" recurse করে ways যোগ করা — ছোট sum-এর ways-গুলো যোগ।
```text
ways(s): # sum s বানানোর ordered sequence-সংখ্যা
if s == 0: return 1 # খালি sequence একটা valid উপায়
if s < 0: return 0
return sum( ways(s - c) for every coin c )
answer = ways(x) % MOD
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **exponential** — প্রতিটা sum-এ প্রতিটা coin একটা শাখা, আর একই sum বহু পথ দিয়ে বারবার গোনা হয় (overlapping subproblems)। sequence-গুলো গাছের পাতা, আর তাদের সংখ্যা exponentially বাড়ে। CSES-এর বড় `x`-এ সম্পূর্ণ অসম্ভব।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct sum মাত্র `x + 1`-টা।** প্রতিটা sum-এর ways একবার গুনে রাখলে, প্রতিটা শুধু কয়েকটা ছোট sum যোগ করে — exponential কাজ O(x × n)-এ নেমে আসে। আর ordered গোনার চাবি: coin-loop **ভেতরে** রাখা (প্রতি sum-এ সব coin শেষে বসানোর সুযোগ)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[s]` = sum `s` বানানোর **ordered** coin sequence-এর সংখ্যা (mod `10^9+7`)।
**Transition:**
```text
dp[s] = sum( dp[s - c] for every coin c with c <= s )
```
কারণ: শেষ coin `c`-এর প্রতিটা পছন্দ disjoint দল; বাকিটা একটা ordered sequence sum `s - c`।
**Base case:** `dp[0] = 1` (একটাই উপায়: কোনো coin না ফেলা — খালি sequence)। Counting বলে base 1, minimizing-এর মতো 0/infinity নয়।
**Answer location:** `dp[x]`।
Memoization (top-down): উপরের `ways(s)` recursion, cache যোগ। Tabulation (bottom-up): `s = 1, 2, ..., x` বাঁ-থেকে-ডান, প্রতিটায় সব coin যোগ — **outer loop = sum, inner loop = coin**। এই order-ই ordered গোনা নিশ্চিত করে (একই multiset-এর প্রতিটা ordering আলাদা)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব sequence enumerate করব" না ভেবে শুধু **শেষ coin**-টা ঠিক করো — বাকিটা ছোট একই problem। আর ordered-vs-unordered-এর crucial শিক্ষা: **loop order**। sum বাইরে / coin ভেতরে = ordered (`[2,3]` ≠ `[3,2]`)। coin বাইরে / sum ভেতরে = unordered (multiset, Coin Combinations II)। একই recurrence, শুধু দুই loop-এর বিন্যাস বদলে অর্থ পাল্টে যায় — এটা মনে রাখার মতো।
### ছবিতে বোঝা {#7-visual-explanation}
`coins = [2, 3, 5]`। `dp[s]` মানে মোট `s` বানানোর ordered sequence-এর সংখ্যা। শেষ coin আলাদা হলে sequence-ও আলাদা।
| s | শেষে 2 বসালে | শেষে 3 বসালে | শেষে 5 বসালে | dp[s] |
| --- | --- | --- | --- | --- |
| 0 | প্রযোজ্য নয় | প্রযোজ্য নয় | প্রযোজ্য নয় | 1: খালি sequence |
| 1 | 0 | 0 | 0 | 0 |
| 2 | dp[0] = 1 | 0 | 0 | 1 |
| 3 | dp[1] = 0 | dp[0] = 1 | 0 | 1 |
| 4 | dp[2] = 1 | dp[1] = 0 | 0 | 1 |
| 5 | dp[3] = 1 | dp[2] = 1 | dp[0] = 1 | 3 |
| 6 | dp[4] = 1 | dp[3] = 1 | dp[1] = 0 | 2 |
| 7 | dp[5] = 3 | dp[4] = 1 | dp[2] = 1 | 5 |
| 8 | dp[6] = 2 | dp[5] = 3 | dp[3] = 1 | 6 |
| 9 | dp[7] = 5 | dp[6] = 2 | dp[4] = 1 | 8 |
```text
s : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
dp: [1] [0] [1] [1] [1] [3] [2] [5] [6] [8]
sum 5: [2,3] [3,2] [5] -> 3 sequences
sum 9: [2,2,5] [2,5,2] [5,2,2] [3,3,3]
[2,2,2,3] [2,2,3,2] [2,3,2,2] [3,2,2,2] -> 8 sequences
```
`dp[5]`-এ একক coin `[5]` বাদ দেওয়া যাবে না। তাই ওই cell-এ 3, এবং পরের cell-গুলোও এই 3 ব্যবহার করেই হিসাব করতে হবে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`coins = [1, 2]`, `x = 4`, tabulation:
1. `dp[0] = 1`
2. `dp[1] = dp[0] = 1` (শুধু coin 1)
3. `dp[2] = dp[1] + dp[0] = 1 + 1 = 2` (1+1, বা 2)
4. `dp[3] = dp[2] + dp[1] = 2 + 1 = 3`
5. `dp[4] = dp[3] + dp[2] = 3 + 2 = 5`
6. return `dp[4] = 5`
হাতে মিলিয়ে: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 = 5 টা ordered way। ✔ (এটা ঠিক Fibonacci — coins {1,2} মানে climbing stairs!)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
MOD = 10**9 + 7
# ---- way 1: tabulation (bottom-up) — sum বাইরে, coin ভেতরে = ordered ----
def coin_comb_ordered_tab(coins, x):
dp = [0] * (x + 1)
dp[0] = 1 # base: খালি sequence
for s in range(1, x + 1): # outer: sum
total = 0
for c in coins: # inner: coin (ordered)
if c <= s:
total += dp[s - c]
dp[s] = total % MOD
return dp[x]
# ---- way 2: memoization (top-down) ----
def coin_comb_ordered_memo(coins, x):
memo = {0: 1}
def ways(s): # sum s-এর ordered ways
if s < 0:
return 0
if s in memo:
return memo[s]
total = 0
for c in coins:
total += ways(s - c)
memo[s] = total % MOD
return memo[s]
return ways(x)
# ---- tests ----
cases = [
([2, 3, 5], 9, 8), # CSES sample
([1, 2], 4, 5), # Fibonacci-মতো (climbing stairs)
([3], 9, 1), # শুধু 3+3+3
([1], 5, 1), # শুধু 1+1+1+1+1
([3], 7, 0), # অসম্ভব
([2, 3], 7, 3), # 2+2+3, 2+3+2, 3+2+2
]
for coins, x, want in cases:
assert coin_comb_ordered_tab(coins, x) == want, (coins, x, coin_comb_ordered_tab(coins, x))
assert coin_comb_ordered_memo(coins, x) == want, (coins, x, coin_comb_ordered_memo(coins, x))
# mod overflow sanity: বড় x-এ crash না করে চলবে
assert coin_comb_ordered_tab([1, 2, 3], 1000) >= 0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `coin_comb_ordered_tab`: `dp[0]=1` (base); outer loop sum, inner loop coin — এই order ordered গোনা নিশ্চিত করে; প্রতিটা `dp[s]` সব coin-এর `dp[s-c]` যোগ, `% MOD`; answer `dp[x]`।
- `coin_comb_ordered_memo`: `ways(s)` sum `s`-এর ordered ways; `s<0` → 0, `s==0` → 1; সব coin শেষে বসিয়ে যোগ; `memo` (dict) repeated কাজ এড়ায়।
- `MOD` প্রতিটা addition-এর পরে নেওয়া হয় যাতে সংখ্যা বড় না হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ ছয়টা input — CSES sample `[2,3,5], 9 -> 8`, একটা `[1,2], 4 -> 5` (যা গোপনে Fibonacci/climbing stairs), দুটো single-coin (`1` ও `0`), আর একটা যাচাই-যোগ্য `[2,3], 7 -> 4`। শেষে একটা বড় `x=1000` mod-overflow sanity check। প্রতিটার জন্য দুই function-ই মিলতে হবে। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
দুই version-ই **O(x × n)** — প্রতিটা sum-এ প্রতিটা coin একবার (`n` = coin-সংখ্যা)।
### অতিরিক্ত জায়গা {#19-space-complexity}
- Tabulation: **O(x)** — `dp` array।
- Memoization: **O(x)** — dict + recursion stack।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Loop order উল্টে ফেলা (coin বাইরে, sum ভেতরে) — তখন **unordered** গোনা হয় (Coin Combinations II), উত্তর কম আসে; ordered-এর জন্য sum বাইরে।
- `dp[0] = 1` না বসানো — পুরো count শূন্য হয়ে যায়, কারণ base identity ভুল (counting শুরু 1 দিয়ে)।
- `% MOD` নিতে ভুলে যাওয়া — বড় `x`-এ সংখ্যা overflow করে CSES-এ Wrong Answer (Python-এ overflow নেই কিন্তু উত্তর mod না নিলে ভুল মান)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #4 Dice Combinations-এর ordered counting + #10 Coin Change-এর unbounded coin loop। [../state-transition-thinking.md](../state-transition-thinking.md)-এর "Problem 1 — Climbing Stairs" আর "Problem 3 — Coin Change"-এর সংমিশ্রণ; [../patterns.md](../patterns.md)-এর "Unbounded counting" family-ও এখানে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Coin Combinations II (unordered/multiset গোনো — loop order বদলায়) —