149 — Combinatorics with DP

Counting জোড়ার দ্বিতীয়টা — আর এই level-এর আরেকটা interview-আত্মীয় idea (climbing-stairs ঘরানার "কয় উপায়ে" প্রশ্ন এর কাছাকাছি)। Level 3-এর Catalan (049) আর Pascal (042) এবার DP-র চোখে। মূল ছাঁচ: "কয় উপায়ে?" প্রশ্নের উত্তর — state-এ "এ পর্যন্ত যা বানিয়েছি তার সারাংশ" রেখে উপায়সংখ্যা যোগ করা। মনে রাখো, এই level সামগ্রিকভাবে CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী)।

Source

• Original source: Counting DP (Catalan via balanced brackets)
• Platform: CSES Counting Problems — https://cses.fi/problemset/
• Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
• Difficulty: Hard
• Pattern: counting DP (state = সারাংশ, মান = উপায়সংখ্যা)
• Basic idea inherited from: 049 (Catalan), 042 (Pascal's triangle)

1. Problem in simple words

n জোড়া bracket দিয়ে কতগুলো valid (সঠিকভাবে মেলানো) sequence বানানো যায়? "Valid" মানে — প্রতিটা খোলা bracket-এর জন্য পরে একটা বন্ধ bracket আছে, আর কোনো prefix-এ বন্ধ bracket খোলার চেয়ে বেশি নেই।

উদাহরণ: n = 3 জোড়া। উত্তর 5 — ((())), (()()), (())(), ()(()), ()()()। (n = 1 → 1, n = 2 → 2)।

এই সংখ্যাগুলোই বিখ্যাত Catalan number (1, 2, 5, 14, 42, ...)। আমরা এগুলো বের করব counting DP-তে: state = "এ পর্যন্ত কয়টা খোলা bracket অমীমাংসিত", মান = "সেই অবস্থায় কয় উপায়ে পৌঁছানো গেল"।

এটা CP-leaning level। Interview-পথে থাকলে এই counting-DP idea-টা শিখে রাখো (DP topic ../../12-dynamic-programming/-এ পূর্ণ রূপ); বাকি CP-material পরে।

2. What is the math idea?

মূল ধারণা counting DP — "কয় উপায়ে" প্রশ্নকে state + যোগে ভাঙা:

state = এ পর্যন্ত যা বানিয়েছি তার সারাংশ (পুরো history নয়!)
মান   = সেই state-এ পৌঁছানোর মোট উপায়সংখ্যা
transition = প্রতিটা সম্ভাব্য পরের পদক্ষেপে উপায়সংখ্যা যোগ করে ছড়াও

Bracket-এ state = এখন কয়টা bracket খোলা (অমীমাংসিত)। প্রতি ধাপে দুই পদক্ষেপ: ( বসাও (খোলা +1, যদি n-এর বেশি না হয়) বা ) বসাও (খোলা −1, যদি negative না হয়)। পেছনে আছে একই গণিত যা Pascal-এ ছিল — প্রতিটা ঘরে আগত পথের যোগফল; আর শেষে যা পাই তা Catalan number।

3. Which basic idea does this inherit from?

দুই শিকড়: Catalan (049) আর Pascal's triangle (042)। 049 থেকে এসেছে balanced bracket / Catalan-এর ধারণা — হয়তো সেখানে closed-form (C(2n,n)/(n+1)) বা recurrence দিয়ে শিখেছিলে। 042 থেকে এসেছে "প্রতি ঘর = আগের ঘরগুলোর যোগ" — DP-তে উপায়সংখ্যা জমানোর মূল চাল।

নতুন idea: Catalan-কে একটা explicit counting DP-তে ফেলা — state হিসেবে "অমীমাংসিত খোলা bracket"। এই state-নির্বাচন (পুরো sequence নয়, শুধু "কয়টা খোলা") counting DP-র মূল শিল্প। তাই এটা 049 আর 042-এর মিলন, DP-র চশমায়।

4. Real-life analogy

ভাবো তুমি ধাপে ধাপে একটা টাওয়ার বানাচ্ছ, আর প্রতি মুহূর্তে শুধু একটা সংখ্যা মনে রাখছ — "এই মুহূর্তে কতগুলো ব্লক ভারসাম্যহীন ঝুলছে (অমীমাংসিত খোলা bracket)"। পুরো টাওয়ারটা কেমন দেখতে সেটা মনে রাখার দরকার নেই — শুধু এই একটা সংখ্যাই ভবিষ্যৎ সিদ্ধান্তের জন্য যথেষ্ট।

প্রতি ধাপে দুটো পথ: নতুন একটা ঝুলন্ত ব্লক যোগ করো ((), বা একটা ঝুলন্ত ব্লক মীমাংসা করো ())। অনেক ভিন্ন টাওয়ার একই "ঝুলন্ত সংখ্যা"-য় থাকতে পারে — তাই আমরা সেই সংখ্যা অনুযায়ী "কয় উপায়ে এখানে এলাম" জমাই। শেষে সব ঝুলন্ত ব্লক মীমাংসিত (0 খোলা) — কয় উপায়ে সেখানে পৌঁছানো গেল, সেটাই উত্তর।

5. Visual explanation

Counting DP-র state ছড়ানো (n = 2, dp[খোলা bracket] = উপায়সংখ্যা):

দৈর্ঘ্য 2n = 4, প্রতি ধাপে: '(' -> খোলা+1,  ')' -> খোলা−1

খোলা:    0    1    2
শুরু:   [1]
         | \
ধাপ 1:  [0,   1]              শুধু '(' বসানো যায় (খোলা 0 -> 1)
            | \  |
ধাপ 2:  [1,   0,   1]?  ->   আসলে: '((' -> খোলা2, '()' -> খোলা0
         প্রকৃত: খোলা0:1, খোলা2:1   (dp = {0:1, 2:1})
            ...
ধাপ 3:  dp = {1: 2}          ((  -> ) -> খোলা1;  ()  -> ( -> খোলা1
ধাপ 4:  dp = {0: 2}          খোলা1 -> ) -> খোলা0

উত্তর = dp[0] = 2   (sequences: (()) আর ()())... আসলে n=2: (()) , ()()  ✓

প্রতি ঘর <- (পূর্বের খোলা−1, '(' বসিয়ে) + (পূর্বের খোলা+1, ')' বসিয়ে)
n=1..6: dp[0] = 1, 2, 5, 14, 42, 132  ->  Catalan!

লক্ষ করো — আমরা পুরো sequence রাখিনি, শুধু "কয়টা খোলা"-র উপর উপায়সংখ্যা জমিয়েছি।

6. Example input and output

n     valid bracket sequence   Catalan
-------------------------------------------
1     1                        ()
2     2                        (()), ()()
3     5                        ((())) সহ 5টা
4     14
5     42
6     132

closed form যাচাই: C(2n,n)/(n+1)
n=3: C(6,3)/4 = 20/4 = 5 ✓

মূল edge case: n = 0 হলে 1 (খালি sequence শূন্যভাবে valid); আর সংখ্যাগুলো দ্রুত বাড়ে — বড় n-এ mod 10⁹+7 লাগে।

7. Brute force thinking

DP না ভেবে — সব সম্ভাব্য (/)-ক্রম enumerate করো (2^(2n)টা), প্রতিটা valid কিনা চেক করো:

from itertools import product


def count_balanced_brute(n):
    count = 0
    for seq in product("()", repeat=2 * n):        # সব 2^(2n) ক্রম
        balance = 0
        ok = True
        for ch in seq:
            balance += 1 if ch == "(" else -1
            if balance < 0:                         # বন্ধ বেশি -> invalid
                ok = False
                break
        if ok and balance == 0:                     # শেষে সব মীমাংসিত
            count += 1
    return count

এটা সংজ্ঞার হুবহু — ঠিক উত্তর দেয় (count_balanced_brute(3) → 5)। আর DP যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু 2^(2n) ক্রম — দ্রুত অসম্ভব।

8. Why brute force may be slow

ক্রম-সংখ্যা 2^(2n) = 4^n — exponential:

n = 5   ->  4^5  = 1024            (ঠিক আছে)
n = 12  ->  4^12 ≈ 1.6 কোটি         (ধীর)
n = 20  ->  4^20 ≈ 10^12            (অসম্ভব)

counting DP: প্রতি ধাপে ≤ (n+1)টা state, 2n ধাপ  ->  O(n²)

মূল সমস্যা — হাজারো ভিন্ন prefix একই "খোলা সংখ্যা"-য় এসে মেলে; তাদের আলাদা গোনা অপচয়। DP সেগুলোকে এক state-এ জমিয়ে exponential থেকে polynomial-এ নামায়।

9. Better thinking

মূল insight: পুরো sequence মনে রাখার দরকার নেই — শুধু "এখন কয়টা bracket খোলা (অমীমাংসিত)" যথেষ্ট। এটাই state।

dp[open] = এই মুহূর্তে 'open'-টা bracket খোলা, কয় উপায়ে এলাম
2n ধাপ চালাও, প্রতি ধাপে:
  '(' বসাও:  open + 1  (যদি ≤ n)   ->  new[open+1] += dp[open]
  ')' বসাও:  open − 1  (যদি ≥ 0)   ->  new[open−1] += dp[open]
শেষে dp[0] = উত্তর (সব মীমাংসিত)

4^n ক্রম-এর বদলে 2n ধাপ × (n+1) state = O(n²)। একই open-count-এর সব prefix এক cell-এ মেলে — এটাই counting DP-র সাশ্রয়।

10. Thinking tweak

এক লাইনের "আহা": "কয় উপায়ে" প্রশ্ন দেখলেই ভাবো — state কী হবে যেটা পুরো history-র বদলে শুধু "ভবিষ্যৎ সিদ্ধান্তে যা দরকার" তা ধরে? সেই state-এ উপায়সংখ্যা জমাও, transition-এ যোগ করো।

সবচেয়ে বড় শিল্প — সঠিক state বাছা। এখানে "কয়টা খোলা bracket" যথেষ্ট, পুরো sequence নয়; এই সারাংশ-চিন্তাই counting DP-র প্রাণ (concept-notes section 11)। আর বড় n-এ mod 10⁹+7 প্রায় সবসময় সঙ্গী — সংখ্যা বিস্ফোরক হয়।

11. Step-by-step dry run

n = 2 জোড়া bracket — counting DP হাতে চালাই (dp[open] = উপায়):

1. শুরু: dp = {0: 1} (কিছু বসাইনি, 0 খোলা, 1 উপায়)।
2. ধাপ 1: open=0 থেকে: ( → open 1 (new[1] += 1); ) → open −1, বাদ। dp = {1: 1}।
3. ধাপ 2: open=1 থেকে: ( → open 2 (new[2] += 1); ) → open 0 (new[0] += 1)। dp = {2: 1, 0: 1}।
4. ধাপ 3: open=2: ) → open 1 (new[1] += 1); ( বাদ (n-এর বেশি)। open=0: ( → open 1 (new[1] += 1)। dp = {1: 2}।
5. ধাপ 4: open=1: ) → open 0 (new[0] += 2)। dp = {0: 2}।
6. শেষ: dp[0] = 2 — 2টা valid sequence ((()), ()())। ✓ Catalan(2) = 2।

12. Python solution

def count_balanced(n):
    """n জোড়া bracket-এর valid sequence সংখ্যা — counting DP-তে।"""
    dp = {0: 1}                              # dp[open] = কয় উপায়ে open-টা খোলা
    for _ in range(2 * n):
        new = {}
        for open_cnt, ways in dp.items():
            if open_cnt + 1 <= n:            # '(' বসাও (খোলা বাড়ে)
                new[open_cnt + 1] = new.get(open_cnt + 1, 0) + ways
            if open_cnt - 1 >= 0:            # ')' বসাও (খোলা কমে)
                new[open_cnt - 1] = new.get(open_cnt - 1, 0) + ways
        dp = new
    return dp.get(0, 0)                      # শেষে সব মীমাংসিত


from itertools import product


def count_balanced_brute(n):
    """সব 2^(2n) ক্রম enumerate — যাচাইয়ের জন্য।"""
    count = 0
    for seq in product("()", repeat=2 * n):
        bal = 0
        ok = True
        for ch in seq:
            bal += 1 if ch == "(" else -1
            if bal < 0:
                ok = False
                break
        if ok and bal == 0:
            count += 1
    return count


def catalan_closed_form(n):
    """C(2n,n)/(n+1) — স্বাধীন যাচাই।"""
    from math import comb
    return comb(2 * n, n) // (n + 1)


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert [count_balanced(n) for n in range(7)] == [1, 1, 2, 5, 14, 42, 132]

# brute force-এর সাথে মিল (DP সঠিক কিনা)
for n in range(7):
    assert count_balanced(n) == count_balanced_brute(n), n

# Catalan closed form-এর সাথে মিল (তৃতীয় স্বাধীন পথ)
for n in range(9):
    assert count_balanced(n) == catalan_closed_form(n), n

print([count_balanced(n) for n in range(1, 7)])   # [1, 2, 5, 14, 42, 132]
print(count_balanced(5))                           # 42
print("সব test pass!")

13. Line-by-line explanation

    dp = {0: 1}

শুরুর state: কিছু বসাইনি, তাই 0টা খোলা bracket, আর সেখানে 1 উপায়ে এসেছি। dp[open] = "এই মুহূর্তে open-টা খোলা, কয় উপায়ে"।

            if open_cnt + 1 <= n:
                new[open_cnt + 1] = new.get(open_cnt + 1, 0) + ways
            if open_cnt - 1 >= 0:
                new[open_cnt - 1] = new.get(open_cnt - 1, 0) + ways

এটাই DP transition। প্রতিটা বর্তমান state থেকে দুই পদক্ষেপ: ( বসালে খোলা +1 (যদি n-এর বেশি না হয় — মোট n জোড়া), ) বসালে খোলা −1 (যদি negative না হয় — বন্ধ বেশি হলে invalid)। উভয় ক্ষেত্রে ways যোগ হয়ে নতুন state-এ জমে।

    return dp.get(0, 0)

2n পদক্ষেপ শেষে valid sequence-এর সব bracket মীমাংসিত — মানে 0 খোলা। dp[0]-ই মোট উপায়সংখ্যা।

বাকি count_balanced_brute সব ক্রম গোনে (যাচাইয়ের জন্য), catalan_closed_form স্বাধীন সূত্র, আর assert গুলো তিনভাবে মিলিয়ে দেখে: DP, brute force, closed form। সব মিললে সব test pass!।

14. Output walkthrough

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

[1, 2, 5, 14, 42, 132]
42
সব test pass!

প্রথম লাইন n = 1..6-এর valid sequence সংখ্যা — Catalan number। দ্বিতীয় n = 5 → 42। তার আগের সব assert চুপচাপ pass — counting DP, brute force, আর Catalan closed form তিনটাই একমত। সবশেষে সব test pass!।

15. Time complexity

O(n²) — 2nটা পদক্ষেপ, প্রতিটায় সর্বোচ্চ (n+1)টা state ছড়ানো। brute force ছিল O(4^n · n) (exponential) — DP সেটাকে polynomial-এ নামিয়েছে। (Catalan-এর closed-form O(n)-এও পাওয়া যায়, কিন্তু DP-চিন্তা সাধারণ — অন্য counting problem-এও খাটে।)

16. Space complexity

O(n) — প্রতি ধাপে dp dictionary-তে সর্বোচ্চ (n+1)টা state। পুরো 4^n ক্রম কখনো রাখি না — এটাই DP-র সাশ্রয়। (দুটো স্তর — dp আর new — রাখলেও O(n)।)

17. Common mistakes

1. ভুল state বাছা — পুরো sequence state-এ রাখলে আবার exponential; "কয়টা খোলা" এই সারাংশই যথেষ্ট (counting DP-র মূল শিল্প)।
2. Boundary ভুলে যাওয়া — ( বসাতে open+1 ≤ n, ) বসাতে open ≥ 1; না মানলে invalid sequence গোনা হয়।
3. mod ভুলে যাওয়া — Catalan দ্রুত বিশাল; বড় n-এ প্রতি যোগে % (10⁹+7) না নিলে overflow/ভুল।
4. n = 0 ভুল — খালি sequence শূন্যভাবে valid, তাই count_balanced(0) = 1; 0 ভাবলে base ভুল।
5. In-place আপডেট — একই dict-এ লিখলে এক ধাপের মান পরের state দূষিত করে; আলাদা new লাগে।

18. Harder problems that inherit this idea

• CSES — Counting Problems (https://cses.fi/problemset/) — নানা counting DP (tiling, grid path, Catalan-ঘরানা)।
• LeetCode — Unique Binary Search Trees (https://leetcode.com/problems/unique-binary-search-trees/) — সরাসরি Catalan, counting DP।
• LeetCode — Generate Parentheses (https://leetcode.com/problems/generate-parentheses/) — একই state (open/close), গোনার বদলে গঠন।

19. Pattern learned

Counting DP — "কয় উপায়ে" প্রশ্নের ছাঁচ: state = "এ পর্যন্ত যা বানিয়েছি তার সারাংশ" (পুরো history নয়), মান = উপায়সংখ্যা, transition-এ যোগ। balanced bracket-এ state = "কয়টা খোলা" → Catalan। সঠিক state-নির্বাচনই আসল শিল্প; mod 10⁹+7 প্রায়ই সঙ্গী।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "'কয় উপায়ে' + বড় n দেখলে counting DP — state = history-র সারাংশ (bracket-এ 'কয়টা খোলা'), মান = উপায়সংখ্যা, transition-এ যোগ। সঠিক state বাছাই আসল কাজ; mod নাও; balanced bracket → Catalan (1,2,5,14,42)।"

পরের ধাপ → 150 — Constructive Math Problems (শেষ boss — উত্তর বানাও, নয়তো invariant-এ impossible প্রমাণ)। শিকড় → 049 — Catalan, 042 — Pascal's Triangle। পূর্ণ 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" বলা হয়েছে।