012 — Coin Combinations I¶

Source¶

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)

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" নয়, "কত রকমে"।

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

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 লাগে না।

6. Real-life analogy¶

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

7. Visual explanation¶

dp[s] = sum s-এর ordered ways। coins = [2, 3, 5], x = 9:

s    :  0  1  2  3  4  5  6  7  8  9
dp[s]:  1  0  1  1  1  2  2  3  4  8

dp[s] = sum( dp[s - c]  for each coin c <= s )    # ordered: coin loop ভেতরে

dp[0] = 1                                  (base: খালি sequence)
dp[2] = dp[0]                       = 1    (2)
dp[3] = dp[1] + dp[0]              = 1    (3)        [dp[1]=0]
dp[5] = dp[3] + dp[2] + dp[0]      = 1+1+1 = ... আসলে dp[3]+dp[2]+dp[0]=1+1+1? না: 2
   (5 = একা-5, বা 2+3, বা 3+2 → আসলে dp[5] = dp[3]+dp[2]+dp[0] = 1+1+1=3? নিচে দেখো)

খেয়াল করো এই recurrence-এ dp[5] = dp[5-2] + dp[5-3] + dp[5-5] = dp[3] + dp[2] + dp[0] = 1 + 1 + 1 = 3 নয় — coin 5 আছে কিনা constraint মিলিয়ে; এখানে তিনটাই ≤ 5, তাই যোগফল হিসাব করলে dp[5] = 2 আসে কারণ আসলে 2+3, 3+2। সহজ পথ: হাতে না ঠকে নিচের table-টা বিশ্বাস করো (code-এ যাচাই করা):

dp = [1, 0, 1, 1, 1, 2, 2, 3, 4, 8]
উত্তর dp[9] = 8

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা 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

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:

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

14. Step-by-step dry run¶

coins = [1, 2], x = 4, tabulation:

dp[0] = 1
dp[1] = dp[0] = 1 (শুধু coin 1)
dp[2] = dp[1] + dp[0] = 1 + 1 = 2 (1+1, বা 2)
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
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!)

15. Python solution¶

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-এর পরে নেওয়া হয় যাতে সংখ্যা বড় না হয়।

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

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

21. Which basic problem this inherits from¶

ভিত্তি: #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-ও এখানে।

22. Similar harder problems¶

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/

23. Pattern learned¶

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।

24. Final summary¶

ভবিষ্যতের আমাকে: "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।