004 — Dice Combinations¶

Source¶

Original source: CSES Problem Set — Dynamic Programming section
Platform: CSES — https://cses.fi/problemset/task/1633
Topic: dynamic programming
Difficulty: Easy
Pattern: 1D counting DP
Basic idea inherited from: #2 Climbing Stairs — কিন্তু এক/দুই ধাপের বদলে এক থেকে ছয় ধাপ (চওড়া look-back)

1. Problem in simple words¶

একটা সাধারণ ছক্কা (1 থেকে 6 আসে) বারবার গড়িয়ে তুমি একটা মোট যোগফল n বানাতে চাও। কয়টা ভিন্ন ক্রমে (ordered sequence) ছক্কা গড়ালে যোগফল ঠিক n হয়, সেটা গোনো। উত্তর বড় হতে পারে, তাই 10^9 + 7 দিয়ে modulo নিতে হয়।

n = 3 হলে sequence-গুলো:
    1+1+1
    1+2
    2+1
    3
মোট 4 টা ভিন্ন ক্রম

2. Which basic idea does this inherit from?¶

এটা #2 Climbing Stairs-এর হুবহু বড় ভাই। সেখানে শেষ move ছিল 1 বা 2 ধাপ (দুটো option); এখানে শেষ গড়ানোটা 1 থেকে 6 — ছয়টা option। তাই দুই-ঘর look-back হয়ে যায় ছয়-ঘর look-back। কাঠামো এক, শুধু কতদূর পেছনে তাকাই সেটা বদলায়।

3. What is the hidden math or logic?¶

লুকানো logic: যোগফল n-এ পৌঁছানোর শেষ ছক্কাটা হতে পারে 1, 2, 3, 4, 5, বা 6। শেষ ছক্কা যদি k হয়, তার আগে যোগফল ছিল n - k। এই ছয়টা দল disjoint (শেষ ছক্কা আলাদা) আর সব সম্ভাবনা cover করে। তাই n-এর ways = (n-1), (n-2), ..., (n-6)-এর ways-এর যোগফল।

4. Which data structure is needed?¶

একটা array dp (size n+1), যেখানে dp[s] = যোগফল s বানানোর ordered sequence-এর সংখ্যা। এখানে rolling-variable trick কম স্বাভাবিক, কারণ পেছনের ছয়টা cell লাগে — তাই পুরো array রাখাই পরিষ্কার।

5. Why this data structure fits¶

State একটামাত্র সংখ্যা: এখন পর্যন্ত যোগফল s। তাই index দিয়ে চলা flat array নিখুঁত — dp[s] যোগফল s-এর উত্তর ধরে। প্রতিটা cell তার পেছনের ছয়টা cell পড়ে, তাই বাঁ-থেকে-ডান ভরলে dependency সবসময় আগেই তৈরি থাকে।

6. Real-life analogy¶

ভাবো তুমি একটা মই বেয়ে উঠছ, কিন্তু এবার একসাথে 1 থেকে 6 ধাপ পর্যন্ত লাফাতে পারো (ছক্কার মতো)। n-তম ধাপে পৌঁছানোর মোট পথ = ঠিক পেছনের ছয়টা ধাপে পৌঁছানোর পথগুলো একসাথে যোগ করা — কারণ শেষ লাফটা সেই ছয়টার যেকোনো একটা থেকে এসেছে।

7. Visual explanation¶

dp[s] = যোগফল s বানানোর ways। ছোট থেকে বড়, প্রতিটা পেছনের ছয়টার যোগফল:

sum  :  0   1   2   3   4    5    6    7
dp   :  1   ?   ?   ?   ?    ?    ?    ?      <- base dp[0] = 1

dp[1] = dp[0]                                  = 1
dp[2] = dp[1] + dp[0]                          = 2
dp[3] = dp[2] + dp[1] + dp[0]                  = 4
dp[4] = dp[3] + dp[2] + dp[1] + dp[0]          = 8
dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]  = 16
dp[6] = dp[5] + dp[4] + dp[3] + dp[2] + dp[1] + dp[0]        = 32
dp[7] = dp[6] + dp[5] + dp[4] + dp[3] + dp[2] + dp[1]        = 63
        (s=7-এ আর dp[0] টানা যায় না, কারণ 7-6=1, তাই dp[1]..dp[6])

sum  :  0   1   2   3   4    5    6    7
dp   :  1   1   2   4   8   16   32   63

খেয়াল করো: প্রথম ছয়টা মান 2-এর ঘাত (powers of 2), তারপর window পেছনে সরে যায়।

8. Example input and output¶

Input : n = 1  -> Output: 1     (শুধু একটা 1)
Input : n = 2  -> Output: 2     (1+1, অথবা 2)
Input : n = 3  -> Output: 4

Edge case 1: n = 6  -> Output: 32
Edge case 2: বড় n  -> উত্তর 10^9+7 দিয়ে modulo নেওয়া (overflow এড়াতে)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য শেষ ছক্কা recurse করে দেখা — 1 থেকে 6, যতক্ষণ overshoot না হয়।

count(s):                        # যোগফল ঠিক s বানানোর ways
    if s == 0: return 1           # পৌঁছে গেছি
    if s < 0:  return 0           # overshoot
    return sum( count(s - k) for k in 1..6 )

10. Why brute force is slow¶

এই recursion exponential (মোটামুটি O(6^n)) — প্রতিটা call ছয়টা ছোট call করে, আর একই যোগফল বারবার গোনা হয় (overlapping subproblems)। count(s-1) আর count(s-2) ইত্যাদি সবাই নিচে গিয়ে আবার একই subproblem ছোঁয়। n সামান্য বড় হলেই (যেমন 30+) এটা কার্যত শেষ হয় না।

11. Key observation¶

মূল observation: distinct যোগফল মাত্র n+1-টা। প্রতিটা যোগফলের ways একবার গুনে রাখলে, প্রতিবার সেটা শুধু পেছনের ছয়টা মান যোগ করে পাওয়া যায় — exponential কাজ O(n)-এ নেমে আসে।

12. Optimized intuition¶

State (শব্দে): dp[s] = ছক্কা গড়িয়ে ঠিক যোগফল s বানানোর ordered sequence-এর সংখ্যা।

Transition:

dp[s] = sum( dp[s - k]  for k = 1..6  if s - k >= 0 )

কারণ: শেষ ছক্কাটা k হলে তার আগে যোগফল ছিল s - k; ছয়টা option disjoint আর সম্পূর্ণ।

Base case: dp[0] = 1 (শূন্য যোগফল বানানোর একটাই উপায়: কোনো ছক্কা না গড়ানো — খালি sequence)।

Answer location: dp[n]।

Memoization (top-down): উপরের count(s) recursion-টাই রাখো, dict যোগ করো। Tabulation (bottom-up): dp[0] = 1 থেকে শুরু করে বাঁ-থেকে-ডান ভরো। বড় উত্তরের জন্য প্রতি যোগে % (10**9 + 7) নাও।

13. Thinking tweak¶

মোচড়: "কতভাবে যোগফল n বানাব" — এই বিশাল প্রশ্নকে বদলে ভাবো "শেষ ছক্কাটা কী ছিল?" উত্তর মাত্র ছয়টা (1..6), তাই বড় count ছয়টা ছোট count-এর যোগফলে ভেঙে যায়। Climbing Stairs-এর দুটো option-কেই এখানে ছয়ে বাড়িয়ে দিলাম — pattern এক।

14. Step-by-step dry run¶

n = 4, tabulation, modulo ছাড়া (ছোট মান):

dp[0] = 1
dp[1] = dp[0] = 1
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4
dp[4] = dp[3] + dp[2] + dp[1] + dp[0] = 4 + 2 + 1 + 1 = 8
return dp[4] = 8

হাতে মিলিয়ে: যোগফল 4-এর ক্রম — 1111, 112, 121, 211, 22, 13, 31, 4 = ঠিক 8 টা। ✔

15. Python solution¶

MOD = 10**9 + 7

# ---- way 1: memoization (top-down) ----
def dice_memo(n):
    memo = {}
    def count(s):
        if s == 0:
            return 1
        if s < 0:
            return 0
        if s in memo:
            return memo[s]
        total = 0
        for k in range(1, 7):
            total += count(s - k)
        memo[s] = total % MOD
        return memo[s]
    return count(n)

# ---- way 2: tabulation (bottom-up) ----
def dice_tab(n):
    dp = [0] * (n + 1)
    dp[0] = 1                                  # base case
    for s in range(1, n + 1):
        for k in range(1, 7):
            if s - k >= 0:
                dp[s] = (dp[s] + dp[s - k]) % MOD
    return dp[n]

# ---- tests ----
expected = [1, 1, 2, 4, 8, 16, 32, 63]        # n = 0..7
for i, want in enumerate(expected):
    assert dice_memo(i) == want, (i, dice_memo(i))
    assert dice_tab(i) == want, (i, dice_tab(i))

assert dice_tab(8) == 125                       # পরের মান
assert dice_memo(50) == dice_tab(50)            # বড় n-এ দুটোই মেলে
assert dice_tab(1000) >= 0                       # modulo-তে overflow নেই
print("সব test pass!")

16. Line-by-line code explanation¶

dice_memo: ভেতরের count(s) যোগফল s-এর ways দেয়; s == 0 base, s < 0 invalid; ছয়টা option যোগ করে % MOD নিয়ে memo-তে রাখে।
dice_tab: dp[0] = 1 base; বাইরের loop যোগফল ছোট-থেকে-বড়, ভেতরের loop ছয়টা শেষ-ছক্কা option; প্রতি যোগে % MOD।
দুই version-ই একই recurrence — একটা recursion-চালিত, একটা loop-চালিত।

17. Output walkthrough¶

expected list-এ n = 0 থেকে 7 পর্যন্ত সঠিক ways (1,1,2,4,8,16,32,63)। দুই function-ই প্রতিটা যাচাই করে; তারপর n = 8-এ 125, n = 50-এ দুই version-এর সমতা, আর n = 1000-এ modulo overflow না-হওয়া check হয়। সব ঠিক থাকলে শেষে print: সব test pass!।

18. Time complexity¶

O(6n) = O(n) — প্রতিটা যোগফলের জন্য সর্বোচ্চ ছয়টা term যোগ হয়। (Naive recursion ছিল প্রায় O(6^n)।)

19. Space complexity¶

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

(চাইলে পেছনের ছয়টা মান rolling করে O(1)-ও করা যায়, কিন্তু window ছয়-চওড়া বলে array রাখাই পরিষ্কার।)

20. Common mistakes¶

dp[0] = 1 না নিয়ে dp[0] = 0 নেওয়া — তখন সব count শূন্য; counting DP-র base সবসময় 1 (খালি sequence)।
modulo নিতে ভুলে যাওয়া — বড় n-এ উত্তর বিশাল হয়ে যায়; CSES-এ wrong answer দেবে।
s - k >= 0 check না করা — negative index Python-এ array-র শেষ থেকে গোনে, নীরবে ভুল ফল দেয়।

21. Which basic problem this inherits from¶

ভিত্তি: #2 Climbing Stairs-এর counting structure, দুই-ঘর look-back-কে ছয়-ঘর করা। ../state-transition-thinking.md-এর counting-base (dp[0]=1) নিয়ম আর ../patterns.md-এর "1D counting" family সরাসরি এখানে।

22. Similar harder problems¶

Coin Combinations I (ছক্কার বদলে নির্দিষ্ট coin set) — https://cses.fi/problemset/task/1635 (এই tracker-এর #12)
Climbing Stairs (দুই-option version) — https://leetcode.com/problems/climbing-stairs/ (#2)
Combination Sum IV (একই ordered counting, যেকোনো target set) — https://leetcode.com/problems/combination-sum-iv/

23. Pattern learned¶

1D counting DP with wide look-back: "কতভাবে?" প্রশ্নে শেষ move-এর সব option (এখানে 1..6) এর ছোট-state ways যোগ করো। Base dp[0] = 1, বড় উত্তরে modulo। Climbing Stairs-এর window চওড়া করলেই এই family।

24. Final summary¶

ভবিষ্যতের আমাকে: "Dice Combinations = Climbing Stairs, কিন্তু শেষ move 1..6, তাই পেছনের ছয়টা cell যোগ।" State 'যোগফল s-এর ways', transition dp[s] = sum(dp[s-k] for k in 1..6), base dp[0]=1, modulo নিতে ভুলো না। Counting DP-তে শেষ decision-এর সব option-এর উপর ভাঙার reflex পাকা করো।

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