Problem link ও উৎস
- **Original source:** LeetCode Unique Paths
- **Platform:** LeetCode —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `m × n` ঘরের grid আছে। তুমি উপরের-বাঁ কোণ থেকে শুরু করে নিচের-ডান কোণে পৌঁছাতে চাও। কিন্তু প্রতি ধাপে শুধু **ডানে (Right)** বা **নিচে (Down)** যেতে পারো — পেছনে বা উপরে নয়।
কতগুলো আলাদা path আছে?
ছোট উদাহরণ: `2 × 2` ঘরের grid — উপরের-বাঁ থেকে নিচের-ডান। path গুলো: ডান→নিচ→নিচ আর নিচ→ডান... (নিচে গুনব)। মূল কথা — তোমাকে নির্দিষ্ট সংখ্যক বার ডানে আর নির্দিষ্ট সংখ্যক বার নিচে যেতেই হবে, শুধু **ক্রম** বদলায়।
### Input ও output {#6-example-input-and-output}
```text
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`।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা শহরের block-grid-এ আছ (যেমন ম্যানহাটন) — রাস্তাগুলো সোজা সোজা, ঘরগুলো আয়তক্ষেত্র। তুমি বাড়ি (উপরের-বাঁ) থেকে অফিসে (নিচের-ডান) যাবে, আর শর্টকাট চাও — তাই কখনো পেছনে যাবে না, শুধু **পূর্বে (ডানে)** আর **দক্ষিণে (নিচে)**।
অফিসে পৌঁছাতে তোমাকে মোট নির্দিষ্ট সংখ্যক block পূর্বে আর নির্দিষ্ট সংখ্যক block দক্ষিণে যেতেই হবে — সেটা যে পথেই যাও। শুধু **কোন মোড়ে পূর্বে আর কোন মোড়ে দক্ষিণে** ঘুরবে, সেই ক্রমটাই path আলাদা করে।
তাই "কয়টা শর্টকাট path" = "পূর্ব আর দক্ষিণ ধাপগুলো কত ভাবে সাজানো যায়" = একটা combination।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা **041 (Combination Basic)**-এর সবচেয়ে জীবন্ত প্রয়োগ। মূল চালাকি: একটা hাঁটার সমস্যাকে "অক্ষর সাজানো"-তে অনুবাদ করা, তারপর সেই সাজানো গুনতে nCr।
কেন nCr? কারণ R-গুলো একই রকম, D-গুলোও একই রকম (একই রকম জিনিস সাজানো)। মোট ধাপের মধ্যে শুধু "R-গুলো কোন কোন জায়গায়" বাছলেই বিন্যাস ঠিক — সেটা খাঁটি combination (041)। এই "সমস্যাকে অন্য চেনা সমস্যায় অনুবাদ" — combinatorics-এর core skill, আর এই problem তার রাজকীয় উদাহরণ।
### ভেতরের অঙ্ক {#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 ঠিক:
```text
path সংখ্যা = C((m−1)+(n−1), n−1) = C(m+n−2, m−1)
```
(LeetCode-এর `m × n` "ঘর" সংখ্যায় এটাই; "ধাপ" সংখ্যায় কথা বললে সরাসরি `C(a+b, a)` — section 6 দেখো।)
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি — **recursion দিয়ে সব path গুনে ফেলা।** প্রতিটা ঘর থেকে হয় ডানে যাও, নয় নিচে:
```python
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):
```text
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:
```python
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 ভরো — প্রতিটা ঘর = উপরের + বাঁ:
```python
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 — সবখানে ফিরবে।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো 2×2 ঘরের grid-এর সব path (ধাপে: 1 R, 1 D):
```text
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-এর জায়গা বাছা:
```text
মোট ধাপ = (m−1) R + (n−1) D
[ _ _ _ _ ] <- (m−1)+(n−1) টা খোপ
এর মধ্যে R-গুলো কোথায় বসবে বাছো:
3×3 ঘর: মোট 4 ধাপ, 2 টা R-এর জায়গা -> C(4, 2) = 6
বাকিগুলো এমনিতেই D
```
লক্ষ করো — R-এর জায়গা ঠিক করলেই D-এর জায়গা আপনাআপনি ঠিক, তাই একটাই combination।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `3 × 3` ঘর — formula `C(3+3−2, 3−1) = C(4, 2) = 6`। DP দিয়েও যাচাই করি:
DP table (প্রথম সারি/column সব 1, বাকি = উপর + বাঁ):
```text
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।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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)`।
```text
def paths_by_steps(r_steps, d_steps):
return comb(r_steps + d_steps, r_steps)
```
"ধাপ" সংখ্যায় সরাসরি — মোট ধাপ থেকে R-ধাপের জায়গা বাছা।
```text
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **"ঘর" আর "ধাপ" গুলিয়ে off-by-one** — m×n **ঘর**-এ R-ধাপ n−1, D-ধাপ m−1; "ঘর" নাকি "ধাপ" আগে ঠিক করো।
2. **Naive recursion রেখে দেওয়া** — overlapping subproblem-এ exponential; formula বা DP নাও।
3. **R আর D অদলবদল ভেবে আলাদা গোনা** — R-গুলো একই, D-গুলো একই; শুধু জায়গা বাছা, সাজানো নয় (তাই permutation নয়, combination)।
4. **এক সারি/column-এ ভুল** — m=1 বা n=1 হলে ঠিক 1 path; formula `C(k, 0) = 1` দেয়, তবু খেয়াল রাখো।
5. **বাধা (obstacle) থাকলে formula খাটানো** — কোনো ঘর blocked হলে সরল nCr চলে না; তখন DP-ই পথ (Unique Paths II)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Unique Paths** (