145 — Probability DP¶

Probability জোড়ার দ্বিতীয়টা। 144-এ দেখলে — যখন সমস্যা সরল টুকরোয় ভাঙা যায়, linearity এক লাইনে মিটিয়ে দেয়। কিন্তু যখন ভাঙা যায় না (ধাপগুলো জট পাকানো)? তখন DP — state-এ probability বয়ে নিয়ে চলা। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী); তবে counting/probability DP-র সাথে interview-র "কয় উপায়ে/কত সম্ভাবনায়" প্রশ্নের আত্মীয়তা আছে।

Source¶

Original source: Classic CP probability-DP pattern (coin/dice state DP)
Platform: Classic CP pattern (USACO Guide — https://usaco.guide/)
Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
Difficulty: Hard
Pattern: probability state (DP-তে সম্ভাবনা বওয়া)
Basic idea inherited from: 144 (Expected Value Problems)

1. Problem in simple words¶

একটা coin (head আসার সম্ভাবনা p) ঠিক k বার toss করা হলো। জিজ্ঞেস: ঠিক h টা head আসার সম্ভাবনা কত? আর বাড়িয়ে: প্রতিটা সম্ভাব্য head-সংখ্যার (0 থেকে k) সম্পূর্ণ সম্ভাবনা-তালিকা চাই।

উদাহরণ: ন্যায্য coin (p = 0.5), k = 3 toss। উত্তর-তালিকা [0.125, 0.375, 0.375, 0.125] — মানে 0 head-এর সম্ভাবনা 0.125, 1 head-এর 0.375, এভাবে।

এটা একটা probability DP-র সরলতম রূপ: প্রতিটা toss-এর পর "এ পর্যন্ত কত head, আর সেই অবস্থায় পৌঁছানোর সম্ভাবনা কত" — এই তথ্যটা state-এ বয়ে নিয়ে যাওয়া।

এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; DP শেখার পরে (../../12-dynamic-programming/) ফিরলে এটা প্রায় ফ্রি লাগবে।

2. What is the math idea?¶

মূল ধারণা probability-কে DP state-এ বওয়া — আর প্রতি ধাপে total probability ভাগ করে ছড়ানো:

dp[h] = এ পর্যন্ত ঠিক h টা head পাওয়ার সম্ভাবনা

প্রতি toss-এ ছড়াও:
  head এলে (সম্ভাবনা p):    head-গণনা 1 বাড়ে  ->  dp[h] এর অংশ যায় new[h+1] এ
  tail এলে (সম্ভাবনা 1-p):  head-গণনা একই      ->  dp[h] এর অংশ যায় new[h] এ

পেছনে আছে law of total probability: একটা অবস্থায় পৌঁছানোর মোট সম্ভাবনা = তার দিকে আসা সব পথের সম্ভাবনার যোগ। DP ঠিক এটাই করে — প্রতি cell-এ সব আগত পথের probability জমায়। আর একটা ফ্রি sanity check: প্রতি ধাপে সব cell-এর যোগফল সবসময় 1।

3. Which basic idea does this inherit from?¶

দাঁড়িয়ে আছে expected value / probability (problem 144)-এর উপর। 144-এ যখন সমস্যা সরল indicator-এ ভাঙা যেত, linearity যথেষ্ট ছিল — কোনো state লাগেনি। কিন্তু এখানে head-গণনা ধাপে ধাপে গড়ায়, প্রতিটা পরের ধাপ আগেরটার উপর নির্ভর — সরল ভাঙা যায় না। তাই 144-এর "ভাঙো-যোগ" বদলে এখানে "state-এ probability বইয়ে transition-এ ছড়াও"।

আর কাঠামোটা চেনা counting-DP-র (যেমন climbing stairs): cell-এ "কয় উপায়ে" রাখার বদলে এখানে "কত সম্ভাবনায়" রাখি, আর transition-এ যোগের জায়গায় probability-গুণ-করে-যোগ। তাই এটা একই সাথে 144 (probability) আর DP-চিন্তার মিলন।

4. Real-life analogy¶

ভাবো একটা জলধারা পাহাড়ের চূড়া থেকে নামছে, পথে পথে দুই ভাগ হয়ে। চূড়ায় 1 লিটার (পুরো সম্ভাবনা)। প্রতিটা কাঁটায় জল ভাগ হয় — কোনো দিকে p অংশ, অন্য দিকে 1−p অংশ।

প্রতিটা toss একটা কাঁটা: head-শাখায় p অংশ জল যায় (head-গণনা বাড়ে), tail-শাখায় 1−p (গণনা একই)। কয়েক স্তর পরে নিচে কয়েকটা পাত্র — প্রতিটা একটা নির্দিষ্ট head-সংখ্যা। প্রতি পাত্রে কত জল জমল = সেই head-সংখ্যা আসার সম্ভাবনা। মোট জল সবসময় 1 লিটার থাকে — কারণ জল হারিয়ে যায় না, শুধু ভাগ হয়। এটাই probability DP।

5. Visual explanation¶

DP table ধাপে ধাপে (ন্যায্য coin, প্রতি ধাপে head শাখায় ও tail শাখায় সমান ভাগ):

dp[h] = এ পর্যন্ত h টা head; প্রতি ধাপে যোগফল 1

শুরু (0 toss):     [1]
                    |
                  ভাগ p / (1-p)
toss 1 পরে:        [0.5,  0.5]            (0 head, 1 head)
                    |  \  /  |
toss 2 পরে:    [0.25, 0.5, 0.25]          (0, 1, 2 head)
                |  \  /  \  /  |
toss 3 পরে: [0.125, 0.375, 0.375, 0.125]  (0,1,2,3 head)

প্রতি cell <- বাম-উপর (head এসে) × p  +  ঠিক-উপর (tail এসে) × (1-p)
যোগফল চেক: 0.125+0.375+0.375+0.125 = 1.0  ✓

এটা Pascal's triangle-এরই probability-রূপ — তাই উত্তর binomial: C(k, h)·pʰ·(1−p)^(k−h)।

6. Example input and output¶

k    p      সম্ভাবনা-তালিকা [0 head, 1, ..., k]
---------------------------------------------------------
3    0.5    [0.125, 0.375, 0.375, 0.125]
2    0.5    [0.25, 0.5, 0.25]
1    0.5    [0.5, 0.5]
4    0.3    [0.2401, 0.4116, 0.2646, 0.0756, 0.0081]
0    0.5    [1.0]                       (toss নেই -> 0 head নিশ্চিত)

দুটো জিনিস খেয়াল করো: যেকোনো সারির যোগফল সবসময় 1 (sanity check); আর k = 0 হলে শুধু [1.0] — কোনো toss নেই মানে 0 head নিশ্চিত।

7. Brute force thinking¶

DP না ভেবে — সব সম্ভাব্য ফলাফল-ক্রম (sequence) enumerate করা। k toss-এর প্রতিটা head/tail হতে পারে, তাই 2^k sequence; প্রতিটার সম্ভাবনা গুণে head গুনে যোগ করি:

from itertools import product


def prob_heads_brute(k, p=0.5):
    dist = [0.0] * (k + 1)
    for seq in product((0, 1), repeat=k):          # 0=tail, 1=head, সব 2^k ক্রম
        h = sum(seq)
        prob = 1.0
        for x in seq:
            prob *= p if x == 1 else (1 - p)
        dist[h] += prob
    return dist

এটা সংজ্ঞার হুবহু — ঠিক উত্তর দেয় (k=3 → [0.125, ...])। আর DP যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু 2^k sequence — তাড়াতাড়ি অসম্ভব হয়ে ওঠে।

8. Why brute force may be slow¶

Sequence-সংখ্যা 2^k — exponential:

k = 10  ->  2^10  ≈ 1000        (ঠিক আছে)
k = 30  ->  2^30  ≈ 100 কোটি    (ধীর)
k = 60  ->  2^60                 (অসম্ভব)

DP: প্রতি ধাপে (k+1)টা cell, k ধাপ  ->  O(k²) — exponential থেকে polynomial!

মূল কথা — একই head-সংখ্যায় পৌঁছানো হাজারো ভিন্ন sequence-কে আলাদা গোনা অপচয়; তাদের শুধু মোট সম্ভাবনা দরকার, যেটা DP cell-এ একসাথে জমে।

9. Better thinking¶

মূল insight: পুরো sequence মনে রাখার দরকার নেই — শুধু "এ পর্যন্ত কত head, আর সেই অবস্থার সম্ভাবনা কত" যথেষ্ট। এটাই state।

dp[h] = এ পর্যন্ত ঠিক h head পাওয়ার সম্ভাবনা
প্রতি toss-এ:
  new[h]   += dp[h] · (1-p)      # tail: head একই
  new[h+1] += dp[h] · p          # head: head বাড়ল

প্রতি ধাপে দুটো শাখায় probability ছড়িয়ে দিই। 2^k sequence-এর বদলে k ধাপ × (k+1) cell = O(k²)। একই head-সংখ্যার সব পথ এক cell-এ মিশে যায় — এটাই DP-র সাশ্রয়।

10. Thinking tweak¶

এক লাইনের "আহা": পুরো random history মনে রেখো না — শুধু যেটুকু ভবিষ্যৎ সিদ্ধান্তে দরকার (এখানে "কত head") সেটাই state-এ রাখো, আর প্রতি ধাপে probability শাখায় শাখায় ছড়িয়ে দাও।

সবচেয়ে কাজের অভ্যাস: প্রতি ধাপে cell-গুলোর যোগফল 1 কিনা চেক করো — এটা ফ্রি sanity check, transition ভুল হলে সাথে সাথে ধরা পড়ে (concept-notes section 7)। আর মনে রাখো — counting DP-তে cell-এ count, এখানে শুধু সেই count-এর জায়গায় probability; কাঠামো হুবহু এক।

11. Step-by-step dry run¶

k = 2, p = 0.5 হাতে চালাই:

শুরু: dp = [1.0] (0 toss, 0 head নিশ্চিত)। আসলে আমরা dp = [1, 0, 0] ধরি (cell 0..k)।
Toss 1: cell 0-এর 1.0 ছড়ায় — tail → new[0] += 1.0×0.5 = 0.5; head → new[1] += 1.0×0.5 = 0.5। dp = [0.5, 0.5, 0]। যোগফল 1.0 ✓।
Toss 2:
cell 0 (0.5): tail → new[0] += 0.25; head → new[1] += 0.25।
cell 1 (0.5): tail → new[1] += 0.25; head → new[2] += 0.25।
dp = [0.25, 0.5, 0.25]। যোগফল 1.0 ✓।
শেষ: [0.25, 0.5, 0.25] — 0 head 0.25, 1 head 0.5, 2 head 0.25। binomial-এর সাথে মেলে।

12. Python solution¶

def prob_heads(k, p=0.5):
    """k বার toss-এ ঠিক h head-এর সম্ভাবনা — তালিকা dp[0..k] ফেরত।"""
    dp = [1.0] + [0.0] * k               # dp[h] = এ পর্যন্ত h head-এর সম্ভাবনা
    for _ in range(k):
        new = [0.0] * (k + 1)
        for h in range(k + 1):
            if dp[h] == 0.0:
                continue
            new[h] += dp[h] * (1 - p)    # tail: head একই
            if h + 1 <= k:
                new[h + 1] += dp[h] * p  # head: head বাড়ল
        dp = new
    return dp


from itertools import product


def prob_heads_brute(k, p=0.5):
    """সব 2^k sequence enumerate — DP যাচাইয়ের জন্য।"""
    dist = [0.0] * (k + 1)
    for seq in product((0, 1), repeat=k):
        prob = 1.0
        for x in seq:
            prob *= p if x == 1 else (1 - p)
        dist[sum(seq)] += prob
    return dist


# --- ছোট test গুলো (সব pass করা উচিত) ---
d3 = prob_heads(3)
assert abs(sum(d3) - 1.0) < 1e-12               # যোগফল সবসময় 1
assert all(abs(a - b) < 1e-12 for a, b in
           zip(d3, [0.125, 0.375, 0.375, 0.125]))

# binomial-এর সাথে মিল (closed form)
from math import comb
for k in range(7):
    for p in (0.5, 0.3, 0.75):
        dp = prob_heads(k, p)
        for h in range(k + 1):
            expected = comb(k, h) * p ** h * (1 - p) ** (k - h)
            assert abs(dp[h] - expected) < 1e-12, (k, p, h)

# brute force-এর সাথে মিল
for k in range(0, 9):
    for p in (0.5, 0.4):
        dp = prob_heads(k, p)
        bf = prob_heads_brute(k, p)
        assert all(abs(a - b) < 1e-12 for a, b in zip(dp, bf)), (k, p)

print([round(x, 3) for x in prob_heads(3)])        # [0.125, 0.375, 0.375, 0.125]
print([round(x, 4) for x in prob_heads(4, 0.3)])   # [0.2401, 0.4116, ...]
print(round(sum(prob_heads(5, 0.6)), 10))          # 1.0
print("সব test pass!")

13. Line-by-line explanation¶

    dp = [1.0] + [0.0] * k

শুরুর state: 0 toss-এ 0 head নিশ্চিত, তাই dp[0] = 1.0, বাকি সব 0। এই dp[h] মানে "এ পর্যন্ত ঠিক h head পাওয়ার সম্ভাবনা"।

            new[h] += dp[h] * (1 - p)
            if h + 1 <= k:
                new[h + 1] += dp[h] * p

এটাই DP transition। বর্তমান cell dp[h]-এর probability দুই শাখায় ছড়ায়: tail এলে (1−p) head একই থাকে → new[h]; head এলে (p) head বাড়ে → new[h+1]। সব আগত অংশ যোগ হয়ে নতুন cell-এর মোট probability।

        dp = new

এক toss-এর হিসাব শেষে dp আপডেট করে পরের toss-এ যাই।

বাকি prob_heads_brute সব sequence গোনে (যাচাইয়ের জন্য), আর assert গুলো তিনভাবে মিলিয়ে দেখে: (১) যোগফল 1, (২) binomial closed form, (৩) brute force। সব মিললে সব test pass!।

14. Output walkthrough¶

চালালে ছাপবে:

[0.125, 0.375, 0.375, 0.125]
[0.2401, 0.4116, 0.2646, 0.0756, 0.0081]
1.0
সব test pass!

প্রথম লাইন ন্যায্য coin 3 toss-এর head-distribution। দ্বিতীয় biased coin (p=0.3) 4 toss। তৃতীয় — যেকোনো distribution-এর যোগফল ঠিক 1.0 (sanity check)। তার আগের সব assert চুপচাপ pass — DP, binomial সূত্র, আর brute force তিনটাই একমত। সবশেষে সব test pass!।

15. Time complexity¶

O(k²) — kটা toss, প্রতিটায় (k+1)টা cell ছড়ানো। brute force ছিল O(2^k · k) (exponential) — DP সেটাকে polynomial-এ নামিয়েছে। (একই head-সংখ্যার সব পথ এক cell-এ মেলায় বলে।)

16. Space complexity¶

O(k) — শুধু একটা dp array (k+1 ঘর), প্রতি ধাপে new দিয়ে আপডেট। পুরো 2^k history কখনো রাখি না — এটাই DP-র মূল সাশ্রয়।

17. Common mistakes¶

যোগফল 1 চেক না করা — transition ভুল হলে সবচেয়ে দ্রুত ধরা পড়ে cell-যোগফল ≠ 1 দেখে; এই ফ্রি check বাদ দিও না।
head/tail-এ p আর 1−p উল্টে ফেলা — head শাখায় p, tail শাখায় 1−p; biased coin-এ উল্টে ফেললে distribution উল্টে যায়।
Boundary (h+1 <= k) ভুলে যাওয়া — সর্বোচ্চ head-এর cell থেকে আর head বাড়ানো যায় না; index error বা ভুল।
Probability আর count গুলিয়ে ফেলা — কাঠামো একই, কিন্তু probability-তে ভগ্নাংশ গুণ হয় (count-এ শুধু যোগ); float ব্যবহার করো।
In-place আপডেট — একই array-তে সরাসরি লিখলে এক toss-এর মান পরের cell-কে দূষিত করে; আলাদা new array লাগে (বা সাবধানী ক্রম)।

18. Harder problems that inherit this idea¶

USACO Guide — Probability & Expected Value DP (https://usaco.guide/) — state-এ probability/expectation বওয়ার নানা problem।
LeetCode — New 21 Game (https://leetcode.com/problems/new-21-game/) — score-state-এ probability DP, sliding window optimization।
LeetCode — Knight Probability in Chessboard (https://leetcode.com/problems/knight-probability-in-chessboard/) — board-state-এ probability ছড়ানো।

19. Pattern learned¶

Probability DP — যখন linearity-তে সরাসরি ভাঙা যায় না, তখন state-এ probability (বা expectation) রাখো, transition-এ শাখায় শাখায় ছড়াও। counting DP-র কাঠামো, শুধু cell-এ count-এর বদলে probability; প্রতি ধাপে যোগফল 1 = ফ্রি sanity check।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "ধাপে-ধাপে randomness যেটা linearity-তে ভাঙে না — probability DP। state = যেটুকু ভবিষ্যতে দরকার (যেমন 'কত head'), প্রতি ধাপে p / (1−p) শাখায় probability ছড়াও। প্রতি স্তরে যোগফল 1 চেক করো।"

পরের ধাপ → 146 — Burnside Lemma Intro (একদম আলাদা স্বাদ — symmetry-র নিচে গোনা)। শিকড় → 144 — Expected Value Problems। পূর্ণ DP → ../../12-dynamic-programming/।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

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