012 — Coin Combinations I

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: CSES Problem Set — Dynamic Programming section
• Platform: CSES — https://cses.fi/problemset/task/1635
• Topic: dynamic programming
• Difficulty: Medium
• Pattern: Unbounded counting
• Basic idea inherited from: #4 Dice Combinations (ordered counting) আর #10 Coin Change (unbounded coin loop)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

n-টা coin-এর মান দেওয়া, প্রত্যেকটার supply অসীম, আর একটা target sum x। ঠিক x বানানোর কতগুলো ordered উপায় (coin sequence) আছে গোনো — মানে [2, 3] আর [3, 2] আলাদা গোনা হয়। উত্তর বড় হতে পারে, তাই 10^9 + 7 দিয়ে modulo নাও। এটা #10-এর "ways গোনো" সংস্করণ — "সবচেয়ে কম coin" নয়, "কত রকমে"।

উদাহরণ

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

উদাহরণ

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-এর গুণিতক নয়)

চেনা উদাহরণে বোঝা

ভাবো তুমি ঠিক x মূল্যের টোকেন একটার পর একটা ফেলে একটা stack বানাচ্ছ, প্রতিটা টোকেন নির্দিষ্ট কিছু মানের একটা। দুটো stack আলাদা যদি কোনো position-এ টোকেনের মান আলাদা হয় (order matters)। মোট কত রকম stack x-এ শেষ হয়? প্রতিটা সম্ভাব্য সবার উপরের টোকেনের জন্য ভাবো — সেটা সরালে নিচে একটা ছোট valid stack (sum x - c); সব শীর্ষ-টোকেনের ways যোগ করো।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

দুটো ভিত্তি একসাথে। #4 Dice Combinations-এর ordered counting চিন্তা (sequence-এর শেষ ধাপ কী?) আর #10 Coin Change-এর unbounded coin loop (প্রতিটা coin বারবার নেওয়া যায়)। Dice-এ "শেষ roll" 1–6 ছিল; এখানে "শেষ coin" coins-এর যেকোনোটা। মূল মন্ত্র এক: শেষ ধাপের উপর ভাগ করে ছোট subproblem-এর ways যোগ।

ভেতরের যুক্তি

লুকানো 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 আলাদা পথ।

কী দিয়ে তথ্য রাখব

একটা 1D array dp (size x + 1), dp[s] = sum s বানানোর ordered sequence-সংখ্যা (mod 10^9+7)। Top-down করলে একটা dict/cache (sum → count)।

এটি কেন উপযুক্ত

State একটামাত্র সংখ্যা: কত sum বানাতে হবে। sum-কে index ধরা flat array নিখুঁত — dp[s] ঠিক sum s-এর ways ধরে। ordered গোনা বলে loop-এ sum বাইরে, coin ভেতরে — প্রতিটা sum-এ সব coin "শেষে" বসাই, যাতে একই multiset-এর প্রতিটা ordering আলাদা গোনা হয়। এক মাত্রাই যথেষ্ট, কারণ history লাগে না।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা coin "শেষে বসিয়ে" recurse করে ways যোগ করা — ছোট sum-এর ways-গুলো যোগ।

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে

এই recursion exponential — প্রতিটা sum-এ প্রতিটা coin একটা শাখা, আর একই sum বহু পথ দিয়ে বারবার গোনা হয় (overlapping subproblems)। sequence-গুলো গাছের পাতা, আর তাদের সংখ্যা exponentially বাড়ে। CSES-এর বড় x-এ সম্পূর্ণ অসম্ভব।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: distinct sum মাত্র x + 1-টা। প্রতিটা sum-এর ways একবার গুনে রাখলে, প্রতিটা শুধু কয়েকটা ছোট sum যোগ করে — exponential কাজ O(x × n)-এ নেমে আসে। আর ordered গোনার চাবি: coin-loop ভেতরে রাখা (প্রতি sum-এ সব coin শেষে বসানোর সুযোগ)।

আরও কম কাজে সমাধান

State (শব্দে): dp[s] = sum s বানানোর ordered coin sequence-এর সংখ্যা (mod 10^9+7)।

Transition:

উদাহরণ

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 আলাদা)।

ভাবনার পরিবর্তন

মোচড়: "সব 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-এর বিন্যাস বদলে অর্থ পাল্টে যায় — এটা মনে রাখার মতো।

ছবিতে বোঝা

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

উদাহরণ

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-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

দুই version-ই O(x × n) — প্রতিটা sum-এ প্রতিটা coin একবার (n = coin-সংখ্যা)।

অতিরিক্ত জায়গা

• Tabulation: O(x) — dp array।
• Memoization: O(x) — dict + recursion stack।

যে ভুলগুলো এড়াতে হবে

• 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 না নিলে ভুল মান)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: #4 Dice Combinations-এর ordered counting + #10 Coin Change-এর unbounded coin loop। ../state-transition-thinking.md-এর "Problem 1 — Climbing Stairs" আর "Problem 3 — Coin Change"-এর সংমিশ্রণ; ../patterns.md-এর "Unbounded counting" family-ও এখানে।

পরের অনুশীলন

• Coin Combinations II (unordered/multiset গোনো — loop order বদলায়) — https://cses.fi/problemset/task/1636
• Dice Combinations (একই ordered counting, coins = 1..6) — https://cses.fi/problemset/task/1633 (এই tracker-এর #4)
• Combination Sum IV (LeetCode, হুবহু ordered count) — https://leetcode.com/problems/combination-sum-iv/

কৌশলটি মনে রাখুন

Unbounded counting (ordered): state sum s, transition Σ dp[s-c] সব coin-এর উপর, base dp[0]=1, fill order left-to-right with sum outer / coin inner। Loop order-ই ordered (sum outer) বনাম unordered (coin outer) ঠিক করে — counting DP-র সবচেয়ে কুখ্যাত subtlety।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "Coin Combinations I = ordered unbounded counting।" State dp[s] = sum s-এর ordered ways, transition dp[s] = Σ dp[s-c], base dp[0]=1, উত্তর dp[x] (mod 1e9+7)। মনে রেখো: sum loop বাইরে = ordered; coin loop বাইরে = unordered; আর counting-এর base সবসময় 1।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।