011 — Minimizing Coins

Source

• Original source: CSES Problem Set — Dynamic Programming section
• Platform: CSES — https://cses.fi/problemset/task/1634
• Topic: dynamic programming
• Difficulty: Medium
• Pattern: Unbounded knapsack (min)
• Basic idea inherited from: #10 Coin Change — হুবহু একই recurrence, শুধু বড় contest limit আর -1 convention

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 দরকার।

coins = [1, 5, 7], x = 11
সবচেয়ে কম: 5 + 5 + 1 = 3 টা coin
(7 + 1 + 1 + 1 + 1 = 5 টা — খারাপ)

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 সমস্যা নেই।

6. Real-life analogy

ভাবো cashier-এর কাছে নির্দিষ্ট কিছু মানের অসীম কয়েন, আর তাকে ঠিক x টাকা ফেরত দিতে হবে যত কম কয়েনে সম্ভব। প্রতিটা সম্ভাব্য "শেষ কয়েন"-এর জন্য সে ভাবে: "এটা শেষে দিলে বাকি টাকা সবচেয়ে কম কয়েনে কত লাগত?" — তারপর সব বিকল্পের মধ্যে সবচেয়ে অল্প-কয়েনের রাস্তা বেছে নেয়।

7. Visual explanation

dp[s] = sum s-এর min coins। coins = [1, 5, 7], x = 11:

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।

8. Example input and output

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

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা coin "শেষে বসিয়ে" recurse করা — sum থেকে সেই coin বিয়োগ করে বাকিটা একইভাবে সমাধান, সবগুলোর মধ্যে min।

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:

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-টাই এখানকার নতুন জিনিস।

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

15. Python solution

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 দেয়।

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

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 দেবে।

21. Which basic problem this inherits from

ভিত্তি: #10 Coin Change (min)-এর হুবহু recurrence; নতুনত্ব শুধু scale (iterative tabulation) আর -1 convention। ../state-transition-thinking.md-এর "Problem 3 — Coin Change" section-ই এর তত্ত্ব; ../patterns.md-এর "Unbounded knapsack" family-ও এখানে।

22. Similar harder problems

• Coin Change (LeetCode সংস্করণ, একই recurrence) — https://leetcode.com/problems/coin-change/ (এই tracker-এর #10)
• Coin Combinations I (min নয়, ordered ways গোনো) — https://cses.fi/problemset/task/1635 (#12)
• Coin Combinations II (unordered ways) — https://cses.fi/problemset/task/1636

23. Pattern learned

Unbounded knapsack (min), iterative: state sum s, transition 1 + min(dp[s-c]), base dp[0]=0 বাকি infinity, fill order left-to-right। বড় limit-এ tabulation default — recursion stack ঝুঁকি এড়াতে। একই DP কখন bottom-up করতে হয়, সেটাই এখানকার মূল শিক্ষা।

24. Final summary

ভবিষ্যতের আমাকে: "Minimizing Coins = Coin Change-এর contest সংস্করণ, iterative করো।" State dp[s] = sum s-এর min coins, transition dp[s] = 1 + min(dp[s-c]), base dp[0]=0 বাকি infinity, উত্তর dp[x] (INF হলে -1)। মনে রেখো: বড় limit মানে tabulation; আর left-to-right fill = unbounded।

---

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