Problem link ও উৎস
- **Original source:** Classic grid counting DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** Grid DP (counting)
- **Basic idea inherited from:** #2 Climbing Stairs — কিন্তু এক লাইনের বদলে 2D grid-এ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `m × n` grid আছে। তুমি বাঁ-উপরের কোণ (top-left) থেকে শুরু করে ডান-নিচের কোণে (bottom-right) যেতে চাও। প্রতি ধাপে শুধু **ডানে (right)** বা **নিচে (down)** যেতে পারো। কতগুলো আলাদা path আছে, সেটা গোনো।
```text
3 x 3 grid:
S . .
. . .
. . E
S থেকে E-তে যাওয়ার মোট 6 টা আলাদা path
```
### Input ও output {#8-example-input-and-output}
```text
Input : m = 3, n = 3 -> Output: 6
Input : m = 3, n = 7 -> Output: 28
Input : m = 3, n = 2 -> Output: 3
Edge case 1: m = 1, n = 1 -> Output: 1 (শুরু = শেষ, একটাই "path")
Edge case 2: m = 1, n = 5 -> Output: 1 (শুধু ডানে, একটাই path)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা শহরের block-grid, তুমি বাঁ-উপরের চৌরাস্তা থেকে ডান-নিচের চৌরাস্তায় যাচ্ছ, শুধু পূর্ব (ডান) আর দক্ষিণে (নিচ) হাঁটো। যেকোনো চৌরাস্তায় পৌঁছানোর মোট পথ = ঠিক পশ্চিমের চৌরাস্তা থেকে আসা পথ + ঠিক উত্তরের চৌরাস্তা থেকে আসা পথ — কারণ শেষ block-টা ওই দুদিকের একটা থেকেই হাঁটা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি #2 Climbing Stairs-এর counting চিন্তা — "শেষ move কোথা থেকে এলো?" দিয়ে ভাঙা। সেখানে এক লাইনে শেষ move ছিল 1 বা 2 ধাপ; এখানে 2D grid-এ একটা cell-এ ঢোকার শেষ move হয় উপর থেকে, নয় বাঁ থেকে — দুটো option, ঠিক দুটো ছোট cell-এর ways যোগ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: cell `(r, c)`-তে ঢোকার শেষ move-টা এসেছে হয় ঠিক উপরের cell `(r-1, c)` থেকে (একটা down), নয় ঠিক বাঁয়ের cell `(r, c-1)` থেকে (একটা right)। এই দুটো দল disjoint আর সব path cover করে। তাই `(r, c)`-তে পৌঁছানোর path-সংখ্যা = উপরের cell-এর path + বাঁয়ের cell-এর path।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **2D array** `dp` (size `m × n`), যেখানে `dp[r][c]` = start থেকে cell `(r, c)` পর্যন্ত path-এর সংখ্যা। চাইলে শুধু **এক row** রেখে O(n) space-এ করা যায়, কারণ প্রতিটা cell শুধু উপরের আর বাঁয়ের cell পড়ে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State এখানে দুটো সংখ্যা: row `r` আর column `c` — তাই 2D array নিখুঁত। `dp[r][c]` cell `(r,c)`-এর উত্তর ধরে। যেহেতু dependency শুধু উপরে আর বাঁয়ে, row-by-row বাঁ-থেকে-ডান ভরলে দুটো dependency-ই আগে তৈরি; আর শুধু আগের row লাগে বলে এক row-তে compress করা যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা cell থেকে recurse করে দুই দিকের path যোগ করা — ডানে যাও আর নিচে যাও।
```text
paths(r, c): # (r,c) থেকে নিচ-ডান কোণে পথ
if r == m-1 and c == n-1: return 1 # পৌঁছে গেছি
if r >= m or c >= n: return 0 # grid-এর বাইরে
return paths(r+1, c) + paths(r, c+1)
answer = paths(0, 0)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **exponential** (মোটামুটি O(2^(m+n))) — প্রতিটা cell দুটো শাখা খোলে, আর একই cell বহু পথ দিয়ে বারবার গোনা হয় (overlapping subproblems)। মাঝখানের cell-গুলো সবচেয়ে বেশি repeat হয়। grid একটু বড় হলেই এটা অসম্ভব ধীর।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct cell মাত্র `m × n`-টা।** প্রতিটা cell-এর path-সংখ্যা একবার গুনে রাখলে, প্রতিটা শুধু দুটো প্রতিবেশী cell যোগ করে পাওয়া যায় — exponential কাজ O(mn)-এ নেমে আসে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[r][c]` = start cell `(0,0)` থেকে cell `(r, c)` পর্যন্ত পৌঁছানোর distinct path-এর সংখ্যা।
**Transition:**
```text
dp[r][c] = dp[r-1][c] + dp[r][c-1]
```
কারণ: `(r,c)`-তে ঢোকার শেষ move উপর থেকে বা বাঁ থেকে — দুটো disjoint দল।
**Base case:** `dp[0][0] = 1`। প্রথম row আর প্রথম column-এর প্রতিটা cell-এ পৌঁছানোর একটাই দিক, তাই সব 1 (grid-এর বাইরের প্রতিবেশীকে 0 ধরলে এটা এমনিই বেরিয়ে আসে)।
**Answer location:** `dp[m-1][n-1]`।
Memoization (top-down): উপরের `paths(r,c)` recursion-টাই রাখো, dict যোগ করো। Tabulation (bottom-up): প্রথম row/column 1 দিয়ে শুরু করে row-by-row বাঁ-থেকে-ডান ভরো। শুধু আগের row লাগে বলে এক row rolling করে O(n) space।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো path গুনব" না ভেবে প্রতিটা cell-এ ছোট প্রশ্ন করো — "এখানে এলাম কোথা থেকে?" উত্তর মাত্র দুটো (উপর বা বাঁ)। তখন Climbing Stairs-এর এক-মাত্রিক counting সরাসরি দুই-মাত্রায় বসে যায়। Grid DP-র এটাই মূল লাফ: 1D counting-কে দুই দিকের যোগে বাড়ানো।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[r][c]` = start থেকে `(r,c)` পর্যন্ত path। `3 × 3` grid:
```text
প্রথম row আর প্রথম column সব 1 (একটাই দিক দিয়ে যাওয়া যায়):
c=0 c=1 c=2
r=0 1 1 1
r=1 1 ? ?
r=2 1 ? ?
dp[r][c] = dp[r-1][c] + dp[r][c-1]
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6 <- answer
c=0 c=1 c=2
r=0 1 1 1
r=1 1 2 3
r=2 1 3 6
```
প্রতিটা cell = উপরের cell + বাঁয়ের cell। (এটা আসলে Pascal's triangle, ঘুরিয়ে।)
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`m = 3, n = 2`, tabulation:
1. প্রথম column সব 1: `dp[0][0]=dp[1][0]=dp[2][0]=1`
2. প্রথম row সব 1: `dp[0][0]=dp[0][1]=1`
3. dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
4. dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
5. return `dp[2][1] = 3`
হাতে মিলিয়ে: 3 সারি 2 কলামে — DDR, DRD, RDD = ঠিক 3 টা path। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import math
# ---- way 1: memoization (top-down) ----
def unique_paths_memo(m, n):
memo = {}
def paths(r, c):
if r == 0 or c == 0: # প্রথম row/column: একটাই path
return 1
if (r, c) in memo:
return memo[(r, c)]
memo[(r, c)] = paths(r - 1, c) + paths(r, c - 1)
return memo[(r, c)]
return paths(m - 1, n - 1)
# ---- way 2: tabulation (bottom-up), full grid ----
def unique_paths_tab(m, n):
dp = [[1] * n for _ in range(m)] # প্রথম row/column 1 দিয়ে initialized
for r in range(1, m):
for c in range(1, n):
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
return dp[m - 1][n - 1]
# ---- way 3: O(n) space (এক row rolling) ----
def unique_paths_row(m, n):
row = [1] * n
for _ in range(1, m):
for c in range(1, n):
row[c] += row[c - 1] # row[c]=উপর (পুরোনো), row[c-1]=বাঁ (নতুন)
return row[n - 1]
# ---- tests ----
cases = [
(3, 3, 6),
(3, 7, 28),
(3, 2, 3),
(1, 1, 1),
(1, 5, 1),
(5, 1, 1),
(4, 4, 20),
]
for m, n, want in cases:
assert unique_paths_memo(m, n) == want, (m, n, unique_paths_memo(m, n))
assert unique_paths_tab(m, n) == want, (m, n, unique_paths_tab(m, n))
assert unique_paths_row(m, n) == want, (m, n, unique_paths_row(m, n))
# closed-form check: C(m+n-2, m-1)
assert want == math.comb(m + n - 2, m - 1)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `unique_paths_memo`: `paths(r,c)` cell `(r,c)`-এর path-সংখ্যা দেয়; `r==0 or c==0` → 1 (একটাই দিক); `memo` repeated কাজ এড়ায়।
- `unique_paths_tab`: পুরো grid 1 দিয়ে শুরু (প্রথম row/column ঠিক হয়ে যায়); ভেতরের cell-গুলো উপর+বাঁ যোগ; answer `dp[m-1][n-1]`।
- `unique_paths_row`: এক row রাখি; `row[c] += row[c-1]`-এ `row[c]` তখনো পুরোনো (উপরের মান) আর `row[c-1]` নতুন (বাঁয়ের মান) — তাই এক array-তেই কাজ হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ সাতটা (m, n) input আর সঠিক উত্তর — দুটো LeetCode example, কয়েকটা edge (single row/column/cell), আর `4×4 = 20`। প্রতিটার জন্য তিন function মিলতে হবে, এবং উত্তরটা closed-form combination `C(m+n-2, m-1)`-এর সাথেও মেলানো হয় (cross-check)। সব pass হলে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Grid DP (counting); `dp[r][c] = dp[r-1][c] + dp[r][c-1]`। 2D array বানাতে `Array.from` — `.fill([])` নয়।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// full 2D grid: প্রথম row/column 1, ভেতরে উপর+বাঁ
function uniquePathsTab(m, n) {
// প্রতিটা row আলাদা array (shared-ref bug এড়িয়ে)
const dp = Array.from({ length: m }, () => new Array(n).fill(1));
for (let r = 1; r < m; r++) {
for (let c = 1; c < n; c++) {
dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
}
}
return dp[m - 1][n - 1];
}
// O(n) space: এক row rolling
function uniquePathsRow(m, n) {
const row = new Array(n).fill(1);
for (let r = 1; r < m; r++) {
for (let c = 1; c < n; c++) row[c] += row[c - 1]; // row[c]=উপর, row[c-1]=বাঁ
}
return row[n - 1];
}
// closed-form cross-check: C(m+n-2, m-1)
function comb(a, b) { let res = 1; for (let i = 0; i < b; i++) res = res * (a - i) / (i + 1); return Math.round(res); }
// ---- test cases (example + edge) ----
const cases = [[3, 3, 6], [3, 7, 28], [3, 2, 3], [1, 1, 1], [1, 5, 1], [5, 1, 1], [4, 4, 20]];
for (const [m, n, want] of cases) {
assert(uniquePathsTab(m, n) === want, "tab " + m + "x" + n);
assert(uniquePathsRow(m, n) === want, "row " + m + "x" + n);
assert(comb(m + n - 2, m - 1) === want, "comb " + m + "x" + n);
}
console.log("সব JS test pass!");
```
> **JS টীকা:** 2D DP grid বানাতে `Array.from({length: m}, () => new Array(n).fill(1))` — প্রতিটা `() => ...` call **নতুন** row দেয়। `new Array(m).fill(new Array(n))` দিলে সব row **একই array reference** পেত, এক cell বদলালে সব row-তে দেখা যেত (নীরব ভয়ংকর bug)। inner `new Array(n).fill(1)`-এ `1` primitive, তাই সেটা নিরাপদ।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function uniquePaths(m: number, n: number): number {
const dp: number[][] = Array.from({ length: m }, () => new Array