048 — Count Paths in Grid¶

এই problem-টা combinatorics-এর সবচেয়ে সুন্দর "অনুবাদ"-এর উদাহরণ। প্রশ্ন: grid-এ এক কোণ থেকে আরেক কোণে শুধু ডানে আর নিচে গিয়ে কয়টা path? প্রথমে মনে হয় গাছ আঁকতে হবে, recursion লাগবে। কিন্তু একটা জাদু-অনুবাদে পুরোটা এক লাইনের C(m+n, n)-এ নেমে আসে — কারণ প্রতিটা path আসলে R আর D অক্ষরের একটা সাজানো সারি! এই অনুবাদের চোখটাই interview-তে পার্থক্য গড়ে। আর এটাই পরে DP-র হাতেখড়ি।

Source¶

Original source: LeetCode Unique Paths
Platform: LeetCode — https://leetcode.com/problems/unique-paths/
Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
Difficulty: Medium
Pattern: C(m+n, n) (grid path = arranging letters)
Basic idea inherited from: 041 — Combination Basic (path = letter সাজানো = nCr)

1. Problem in simple words¶

একটা m × n ঘরের grid আছে। তুমি উপরের-বাঁ কোণ থেকে শুরু করে নিচের-ডান কোণে পৌঁছাতে চাও। কিন্তু প্রতি ধাপে শুধু ডানে (Right) বা নিচে (Down) যেতে পারো — পেছনে বা উপরে নয়।

কতগুলো আলাদা path আছে?

ছোট উদাহরণ: 2 × 2 ঘরের grid — উপরের-বাঁ থেকে নিচের-ডান। path গুলো: ডান→নিচ→নিচ আর নিচ→ডান... (নিচে গুনব)। মূল কথা — তোমাকে নির্দিষ্ট সংখ্যক বার ডানে আর নির্দিষ্ট সংখ্যক বার নিচে যেতেই হবে, শুধু ক্রম বদলায়।

2. What is the math idea?¶

মূল idea — প্রতিটা path = R আর D অক্ষরের একটা সাজানো সারি।

m × n ঘরের grid-এ এক কোণ থেকে অন্য কোণে যেতে:

ডানে যেতে হবে ঠিক n − 1 বার (column বরাবর)
নিচে যেতে হবে ঠিক m − 1 বার (row বরাবর)

মোট ধাপ (m−1) + (n−1)। প্রতিটা path-ই এই অক্ষরগুলোর একটা বিন্যাস (যেমন RRDD, RDRD...)। কোথায় R বসবে সেটা বাছলেই path ঠিক:

path সংখ্যা = C((m−1)+(n−1), n−1) = C(m+n−2, m−1)

(LeetCode-এর m × n "ঘর" সংখ্যায় এটাই; "ধাপ" সংখ্যায় কথা বললে সরাসরি C(a+b, a) — section 6 দেখো।)

3. Which basic idea does this inherit from?¶

এটা 041 (Combination Basic)-এর সবচেয়ে জীবন্ত প্রয়োগ। মূল চালাকি: একটা hাঁটার সমস্যাকে "অক্ষর সাজানো"-তে অনুবাদ করা, তারপর সেই সাজানো গুনতে nCr।

কেন nCr? কারণ R-গুলো একই রকম, D-গুলোও একই রকম (একই রকম জিনিস সাজানো)। মোট ধাপের মধ্যে শুধু "R-গুলো কোন কোন জায়গায়" বাছলেই বিন্যাস ঠিক — সেটা খাঁটি combination (041)। এই "সমস্যাকে অন্য চেনা সমস্যায় অনুবাদ" — combinatorics-এর core skill, আর এই problem তার রাজকীয় উদাহরণ।

4. Real-life analogy¶

ভাবো তুমি একটা শহরের block-grid-এ আছ (যেমন ম্যানহাটন) — রাস্তাগুলো সোজা সোজা, ঘরগুলো আয়তক্ষেত্র। তুমি বাড়ি (উপরের-বাঁ) থেকে অফিসে (নিচের-ডান) যাবে, আর শর্টকাট চাও — তাই কখনো পেছনে যাবে না, শুধু পূর্বে (ডানে) আর দক্ষিণে (নিচে)।

অফিসে পৌঁছাতে তোমাকে মোট নির্দিষ্ট সংখ্যক block পূর্বে আর নির্দিষ্ট সংখ্যক block দক্ষিণে যেতেই হবে — সেটা যে পথেই যাও। শুধু কোন মোড়ে পূর্বে আর কোন মোড়ে দক্ষিণে ঘুরবে, সেই ক্রমটাই path আলাদা করে।

তাই "কয়টা শর্টকাট path" = "পূর্ব আর দক্ষিণ ধাপগুলো কত ভাবে সাজানো যায়" = একটা combination।

5. Visual explanation¶

প্রথমে দেখো 2×2 ঘরের grid-এর সব path (ধাপে: 1 R, 1 D):

2×2 ঘর -> 1 বার ডানে (R), 1 বার নিচে (D):

S . . .         path 1:  R then D
. . . .         path 2:  D then R
. . . E         মোট 2 = C(2, 1) = 2

বড় case: 3×3 ঘর -> 2 R, 2 D:
RRDD  RDRD  RDDR  DRRD  DRDR  DDRR  -> 6 = C(4, 2)

এবার দেখো অনুবাদটা — path = R/D সারি, R-এর জায়গা বাছা:

মোট ধাপ = (m−1) R + (n−1) D
[ _ _ _ _ ]  <- (m−1)+(n−1) টা খোপ
এর মধ্যে R-গুলো কোথায় বসবে বাছো:

3×3 ঘর: মোট 4 ধাপ, 2 টা R-এর জায়গা -> C(4, 2) = 6
বাকিগুলো এমনিতেই D

লক্ষ করো — R-এর জায়গা ঠিক করলেই D-এর জায়গা আপনাআপনি ঠিক, তাই একটাই combination।

6. Example input and output¶

unique_paths(m, n)  [m×n ঘর] = C(m+n−2, m−1):
   (2, 2)  ->  2
   (3, 3)  ->  6
   (3, 7)  ->  28
   (1, 1)  ->  1     (এক ঘর -> এক path, কোথাও যেতে হয় না)
   (1, 5)  ->  1     (এক সারি -> শুধু ডানে, এক path)
   (3, 2)  ->  3

paths_by_steps(r_steps, d_steps) = C(r+d, r):
   (2, 2)  ->  6     (2 R, 2 D -> RRDD ...)
   (3, 1)  ->  4     (RRRD, RRDR, RDRR, DRRR)

Edge case: এক সারি বা এক column (m=1 বা n=1) → মাত্র 1 path (একদিকেই যাওয়া)। 0 ধাপ (1×1 ঘর) → C(0,0) = 1।

7. Brute force thinking¶

সবচেয়ে সরাসরি — recursion দিয়ে সব path গুনে ফেলা। প্রতিটা ঘর থেকে হয় ডানে যাও, নয় নিচে:

def unique_paths_rec(m, n):
    # m × n ঘর; গন্তব্যে পৌঁছানোর path সংখ্যা
    if m == 1 or n == 1:        # এক সারি/column -> 1 path
        return 1
    return unique_paths_rec(m - 1, n) + unique_paths_rec(m, n - 1)

গল্পটা: শেষ ঘরে আসতে হলে হয় উপরের ঘর থেকে নিচে নেমেছ (m−1, n), নয় বাঁ ঘর থেকে ডানে এসেছ (m, n−1) — দুই path-সংখ্যার যোগ। ছোট grid-এ একদম ঠিক, আর formula verify করার ভালো উপায়।

8. Why brute force may be slow¶

এই recursion একই উপ-grid বারবার গোনে (ঠিক Pascal/Fibonacci-র মতো overlapping subproblem):

unique_paths_rec(3,3) ডাকতে গিয়ে (2,2) বহুবার আলাদা শাখায় ফেরে

গাছটা প্রায় দ্বিগুণ হারে ফোলে -> O(2^(m+n)) মতো
বড় grid (যেমন 20×20)-এ কোটি কোটি call -> Time Limit Exceeded

দুটো সমাধান: (১) DP — উপ-grid-এর উত্তর table-এ জমাও (O(m·n)); (২) আরও ভালো — সরাসরি combination formula (O(min(m,n)))। নিচে দুটোই।

9. Better thinking¶

দুটো উন্নত পথ:

পথ 1 — combination formula (সবচেয়ে দ্রুত): অনুবাদ করো path = R/D সারি, তাই উত্তর সরাসরি একটা nCr:

from math import comb

def unique_paths(m, n):
    # m × n ঘর -> (m−1) D + (n−1) R সাজানো
    return comb(m + n - 2, m - 1)

পথ 2 — DP (overlapping subproblem জমানো): Pascal-এর মতো table ভরো — প্রতিটা ঘর = উপরের + বাঁ:

def unique_paths_dp(m, n):
    dp = [[1] * n for _ in range(m)]        # প্রথম সারি/column সব 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

formula O(min(m,n)), DP O(m·n) — দুটোই brute-এর exponential থেকে বিশাল উন্নতি।

10. Thinking tweak¶

আসল "আহা" মুহূর্ত: hাঁটা ভুলে যাও — প্রতিটা path আসলে R আর D অক্ষরের একটা সাজানো সারি; কত path = সেই অক্ষর কত ভাবে সাজানো যায় = C(মোট ধাপ, R-ধাপ)।

কেন কাজ করে: গন্তব্যে যেতে R আর D-এর সংখ্যা নির্দিষ্ট (grid-ই ঠিক করে দেয়), শুধু ক্রম স্বাধীন। R-গুলো একই, D-গুলো একই — তাই শুধু "R-গুলোর জায়গা" বাছলেই path ঠিক। এই "process-কে object-সাজানোয় অনুবাদ" মোচড়টাই combinatorics-এর সবচেয়ে দামি দক্ষতা — barrier, lattice path, sequence — সবখানে ফিরবে।

11. Step-by-step dry run¶

চলো 3 × 3 ঘর — formula C(3+3−2, 3−1) = C(4, 2) = 6। DP দিয়েও যাচাই করি:

DP table (প্রথম সারি/column সব 1, বাকি = উপর + বাঁ):

       j=0  j=1  j=2
i=0:    1    1    1
i=1:    1    2    3        (2 = 1+1, 3 = 1+2)
i=2:    1    3    6        (3 = 1+2, 6 = 3+3)
                  ^
            গন্তব্য = 6

হাতে যাচাই (অক্ষর): RRDD, RDRD, RDDR, DRRD, DRDR, DDRR — ঠিক 6টা ✓। formula, DP, হাতে-গোনা — তিনটাই 6।

12. Python solution¶

from math import comb


def unique_paths(m, n):
    """m × n ঘরের grid-এ উপর-বাঁ থেকে নিচ-ডান, শুধু R/D: C(m+n−2, m−1)।"""
    return comb(m + n - 2, m - 1)


def paths_by_steps(r_steps, d_steps):
    """r বার ডানে, d বার নিচে -> অক্ষর সাজানো: C(r+d, r)।"""
    return comb(r_steps + d_steps, r_steps)


def unique_paths_dp(m, n):
    """একই উত্তর DP-পথে (overlapping subproblem জমিয়ে)।"""
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]


# --- brute force verifier (recursion-এ সব path গুনে) ---
def unique_paths_rec(m, n):
    if m == 1 or n == 1:
        return 1
    return unique_paths_rec(m - 1, n) + unique_paths_rec(m, n - 1)


# --- ছোট test গুলো (সব pass করা উচিত) ---

# formula সঠিক কিনা
assert unique_paths(2, 2) == 2
assert unique_paths(3, 3) == 6
assert unique_paths(3, 7) == 28
assert unique_paths(1, 1) == 1
assert unique_paths(1, 5) == 1
assert unique_paths(3, 2) == 3

# formula == DP == recursion (ছোট grid জুড়ে)
for m in range(1, 8):
    for n in range(1, 8):
        f = unique_paths(m, n)
        assert f == unique_paths_dp(m, n)
        assert f == unique_paths_rec(m, n)

# paths_by_steps == সরাসরি অক্ষর সাজানো গুনে (brute, itertools)
from itertools import permutations
def paths_brute(r, d):
    seq = "R" * r + "D" * d
    return len(set(permutations(seq)))      # distinct বিন্যাস

assert paths_by_steps(2, 2) == 6 == paths_brute(2, 2)
assert paths_by_steps(3, 1) == 4 == paths_brute(3, 1)
assert paths_by_steps(2, 3) == paths_brute(2, 3)

print(unique_paths(3, 3))        # 6
print(unique_paths(3, 7))        # 28
print(paths_by_steps(2, 2))      # 6
print("সব test pass!")

13. Line-by-line explanation¶

def unique_paths(m, n):
    return comb(m + n - 2, m - 1)

মূল formula — m×n ঘরে (m−1) টা D আর (n−1) টা R, মোট (m+n−2) ধাপ; R বা D-এর জায়গা বাছা = C(m+n−2, m−1)।

def paths_by_steps(r_steps, d_steps):
    return comb(r_steps + d_steps, r_steps)

"ধাপ" সংখ্যায় সরাসরি — মোট ধাপ থেকে R-ধাপের জায়গা বাছা।

    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

DP — প্রথম সারি/column সব 1 (একদিকেই যাওয়া), বাকি প্রতিটা ঘর = উপরের ঘর + বাঁ ঘর (দুই দিক থেকে আসা path-এর যোগ)। ঠিক Pascal-এর "উপরের দুই ঘরের যোগ"।

বাকি assert লাইনগুলো formula, DP, recursion আর অক্ষর-সাজানো brute — চার পথে যাচাই করছে। সব মিললে শেষে সব test pass!।

14. Output walkthrough¶

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

6
28
6
সব test pass!

প্রথম: unique_paths(3,3) = 6 (C(4,2))। দ্বিতীয়: unique_paths(3,7) = 28 (C(8,2))। তৃতীয়: paths_by_steps(2,2) = 6। আগের সব assert (formula = DP = recursion = অক্ষর-brute, চার দিক থেকে cross-check) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity¶

formula unique_paths O(min(m, n)) — একটা comb হিসাব। DP O(m · n) — প্রতিটা ঘর একবার ভরা। recursion brute O(2^(m+n)) — overlapping subproblem-এ exponential। formula-ই দ্রুততম।

16. Space complexity¶

formula O(1)। DP O(m · n) পুরো table (এক সারি রেখে O(n)-এও করা যায়)। recursion O(m + n) call stack।

17. Common mistakes¶

"ঘর" আর "ধাপ" গুলিয়ে off-by-one — m×n ঘর-এ R-ধাপ n−1, D-ধাপ m−1; "ঘর" নাকি "ধাপ" আগে ঠিক করো।
Naive recursion রেখে দেওয়া — overlapping subproblem-এ exponential; formula বা DP নাও।
R আর D অদলবদল ভেবে আলাদা গোনা — R-গুলো একই, D-গুলো একই; শুধু জায়গা বাছা, সাজানো নয় (তাই permutation নয়, combination)।
এক সারি/column-এ ভুল — m=1 বা n=1 হলে ঠিক 1 path; formula C(k, 0) = 1 দেয়, তবু খেয়াল রাখো।
বাধা (obstacle) থাকলে formula খাটানো — কোনো ঘর blocked হলে সরল nCr চলে না; তখন DP-ই পথ (Unique Paths II)।

18. Harder problems that inherit this idea¶

LeetCode — Unique Paths (https://leetcode.com/problems/unique-paths/) — হুবহু এই problem।
LeetCode — Unique Paths II (https://leetcode.com/problems/unique-paths-ii/) — বাধা সহ; formula ভাঙে, DP লাগে।
049 — Catalan Number Intro (এই repo) — diagonal পেরোনো নিষেধ এমন lattice path → Catalan, এই grid-path চিন্তারই বিশেষ রূপ।

19. Pattern learned¶

Lattice path = arranging letters → C(total steps, one direction) — grid path-কে R/D সারিতে অনুবাদ করে nCr; বাধা থাকলে DP (উপর+বাঁ যোগ)। মূল signal: "শুধু ডানে/নিচে গিয়ে কয়টা path" দেখলেই R/D সাজানো — C(m+n−2, m−1)।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "grid path = R/D অক্ষর সাজানো = C(মোট ধাপ, R-ধাপ); m×n ঘরে C(m+n−2, m−1)। বাধা থাকলে DP (উপর+বাঁ)। hাঁটাকে object-সাজানোয় অনুবাদ — এটাই চাবি।"

পরের ধাপ → 049 — Catalan Number Intro (diagonal না-পেরোনো path = balanced bracket = Catalan)।

ফিরে দেখা: আগের ধাপ → 041 — Combination Basic · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

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