Problem link ও উৎস
- **Original source:** Classic grid cost-minimization DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** Grid DP (min)
- **Basic idea inherited from:** #7 Unique Paths — একই right/down grid, কিন্তু `+`-কে `min` দিয়ে বদলানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `m × n` grid দেওয়া, প্রতিটা cell-এ একটা non-negative cost (টাকা) আছে — `grid[r][c]`। তুমি বাঁ-উপরের কোণ (top-left) থেকে ডান-নিচের কোণে (bottom-right) যাবে, প্রতি ধাপে শুধু **ডানে (right)** বা **নিচে (down)**। পথে যত cell ছোঁবে সবগুলোর cost যোগ হবে। সবচেয়ে কম মোট cost-এর path-টা বের করে সেই sum return করো।
```text
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
সবচেয়ে সস্তা path: 1 -> 3 -> 1 -> 1 -> 1 = 7
```
### Input ও output {#8-example-input-and-output}
```text
Input : [[1,3,1],[1,5,1],[4,2,1]] -> Output: 7 (1->3->1->1->1)
Input : [[1,2,3],[4,5,6]] -> Output: 12 (1->2->3->6)
Edge case 1: [[5]] -> Output: 5 (একটাই cell)
Edge case 2: [[1,2,3]] -> Output: 6 (এক row, পুরোটা যোগ)
Edge case 3: [[1],[2],[3]] -> Output: 6 (এক column, পুরোটা যোগ)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা শহরের block-grid, প্রতিটা চৌরাস্তায় একটা toll (টাকা) দিতে হয়। তুমি বাঁ-উপরের চৌরাস্তা থেকে ডান-নিচের চৌরাস্তায় যাবে, শুধু পূর্ব (ডান) আর দক্ষিণে (নিচ) হেঁটে। যেকোনো চৌরাস্তায় পৌঁছানোর সবচেয়ে কম খরচ = ওই চৌরাস্তার toll + (ঠিক পশ্চিম বা ঠিক উত্তরের চৌরাস্তায় পৌঁছানোর খরচের মধ্যে যেটা কম) — কারণ শেষ block-টা ওই দুদিকের একটা থেকেই হাঁটা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি #7 Unique Paths-এর right/down grid চিন্তা — "এই cell-এ ঢুকলাম কোথা থেকে?" দিয়ে ভাঙা। সেখানে দুই দিকের ways **যোগ** করতাম (counting); এখানে দুই দিকের best cost-এর মধ্যে **min** নিয়ে নিজের cost যোগ করি (optimization)। এটা সেই একই pattern, শুধু `+` operator-টা `min`-এ বদলে গেছে — ঠিক যেভাবে #3 Min Cost Climbing Stairs #2 Climbing Stairs থেকে এসেছিল।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: cell `(r, c)`-তে ঢোকার শেষ move হয় ঠিক উপরের cell `(r-1, c)` থেকে (একটা down), নয় ঠিক বাঁয়ের cell `(r, c-1)` থেকে (একটা right)। দুই দিকের যেটার পর্যন্ত পৌঁছানোর cost কম, সেটাই বেছে নিয়ে এই cell-এর নিজের cost যোগ করো। তাই `(r, c)`-তে পৌঁছানোর সবচেয়ে সস্তা মোট cost = `grid[r][c]` + `min`(উপরের best, বাঁয়ের best)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **2D array** `dp` (size `m × n`), যেখানে `dp[r][c]` = start থেকে cell `(r, c)` পর্যন্ত পৌঁছানোর minimum total cost। চাইলে শুধু **এক row** রেখে O(n) space-এ করা যায়, কারণ প্রতিটা cell শুধু উপরের আর বাঁয়ের cell পড়ে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State এখানে দুটো সংখ্যা: row `r` আর column `c` — তাই 2D array নিখুঁত। `dp[r][c]` ঠিক `(r,c)` cell-এর উত্তর ধরে। Dependency শুধু উপরে আর বাঁয়ে বলে row-by-row বাঁ-থেকে-ডান ভরলে দুই dependency-ই আগে তৈরি থাকে; আর শুধু আগের row লাগে বলে এক row-তে compress করে O(n) space।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা cell থেকে recurse করে দুই দিকের min path খোঁজা — ডানে যাও আর নিচে যাও, যেটা কম।
```text
cost(r, c): # (r,c) থেকে নিচ-ডান কোণে min cost
if r == m-1 and c == n-1:
return grid[r][c] # পৌঁছে গেছি
if r >= m or c >= n:
return INF # grid-এর বাইরে, অবৈধ
return grid[r][c] + min(cost(r+1, c), cost(r, c+1))
answer = cost(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 পর্যন্ত min cost একবারই গোনা দরকার — কারণ সেটা শুধু উপরের আর বাঁয়ের cell-এর উপর নির্ভর করে। একবার গুনে রাখলে exponential কাজ O(mn)-এ নেমে আসে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[r][c]` = start cell `(0,0)` থেকে cell `(r, c)` পর্যন্ত পৌঁছানোর minimum total cost (cell `(r,c)`-এর cost সহ)।
**Transition:**
```text
dp[r][c] = grid[r][c] + min( dp[r-1][c], # উপর থেকে এলে
dp[r][c-1] ) # বাঁ থেকে এলে
```
কারণ: `(r,c)`-তে ঢোকার শেষ move উপর থেকে বা বাঁ থেকে; দুই দিকের সস্তাটা বেছে নিজের cost যোগ।
**Base case:** `dp[0][0] = grid[0][0]`। প্রথম row-এ শুধু বাঁ থেকে আসা যায়, তাই `dp[0][c] = dp[0][c-1] + grid[0][c]`; প্রথম column-এ শুধু উপর থেকে, তাই `dp[r][0] = dp[r-1][0] + grid[r][0]` (grid-এর বাইরের neighbor-কে infinity ধরলে এটা এমনিই বেরিয়ে আসে)।
**Answer location:** `dp[m-1][n-1]`।
Memoization (top-down): উপরের `cost(r,c)` recursion-টাই রাখো, dict যোগ করো। Tabulation (bottom-up): প্রথম row/column running-sum দিয়ে শুরু করে row-by-row বাঁ-থেকে-ডান ভরো। শুধু আগের row লাগে বলে এক row rolling করে O(n) space।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো path খুঁজে বের করব" না ভেবে প্রতিটা cell-এ ছোট প্রশ্ন করো — "এখানে এলাম কোথা থেকে, আর সেটা কত খরচে?" উত্তর মাত্র দুটো (উপর বা বাঁ), আর সস্তাটা নাও। Unique Paths-এর যোগের জায়গায় শুধু `min` বসিয়ে দিলেই counting problem optimization problem হয়ে যায় — operator বদলানোর এই reflex-টা DP-তে বারবার লাগবে।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[r][c]` = start থেকে `(r,c)` পর্যন্ত min cost। উপরের `grid`:
```text
grid: dp (পূরণ করতে করতে):
1 3 1 1 4 5
1 5 1 -> 2 9 6
4 2 1 6 8 7
প্রথম row: শুধু বাঁ থেকে আসা যায়, তাই running sum
dp[0][0] = 1
dp[0][1] = 1 + 3 = 4
dp[0][2] = 4 + 1 = 5
প্রথম column: শুধু উপর থেকে আসা যায়, তাই running sum
dp[1][0] = 1 + 1 = 2
dp[2][0] = 2 + 4 = 6
ভেতরের cell: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
dp[1][1] = 5 + min(4, 2) = 5 + 2 = 7 (আরে, নিচে দেখো)
```
খেয়াল করো `dp[1][1]`-এ `min(উপর=4, বাঁ=2) = 2`, তাই `5 + 2 = 7`; কিন্তু আসল best path 5-কে এড়িয়ে যায়, তাই উত্তরের cell-এ 5 ঢোকে না। শেষ cell `dp[2][2] = 7` — সেটাই answer।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`grid = [[1,2,3],[4,5,6]]`, tabulation:
1. `dp[0][0] = 1`
2. প্রথম row: `dp[0][1] = 1 + 2 = 3`, `dp[0][2] = 3 + 3 = 6`
3. প্রথম column: `dp[1][0] = 1 + 4 = 5`
4. `dp[1][1] = 5 + min(dp[0][1], dp[1][0]) = 5 + min(3, 5) = 5 + 3 = 8`
5. `dp[1][2] = 6 + min(dp[0][2], dp[1][1]) = 6 + min(6, 8) = 6 + 6 = 12`
6. return `dp[1][2] = 12`
হাতে মিলিয়ে: path 1->2->3->6 = 12। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
INF = float("inf")
# ---- way 1: memoization (top-down) ----
def min_path_memo(grid):
m, n = len(grid), len(grid[0])
memo = {}
def cost(r, c): # (r,c) থেকে নিচ-ডান কোণে min cost
if r == m - 1 and c == n - 1:
return grid[r][c]
if r >= m or c >= n:
return INF
if (r, c) in memo:
return memo[(r, c)]
memo[(r, c)] = grid[r][c] + min(cost(r + 1, c), cost(r, c + 1))
return memo[(r, c)]
return cost(0, 0)
# ---- way 2: tabulation (bottom-up), full grid ----
def min_path_tab(grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for c in range(1, n): # প্রথম row: শুধু বাঁ থেকে
dp[0][c] = dp[0][c - 1] + grid[0][c]
for r in range(1, m): # প্রথম column: শুধু উপর থেকে
dp[r][0] = dp[r - 1][0] + grid[r][0]
for r in range(1, m):
for c in range(1, n):
dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])
return dp[m - 1][n - 1]
# ---- way 3: O(n) space (এক row rolling) ----
def min_path_row(grid):
m, n = len(grid), len(grid[0])
row = [0] * n
row[0] = grid[0][0]
for c in range(1, n):
row[c] = row[c - 1] + grid[0][c] # প্রথম row
for r in range(1, m):
row[0] += grid[r][0] # column 0: শুধু উপর থেকে
for c in range(1, n):
row[c] = grid[r][c] + min(row[c], row[c - 1]) # row[c]=উপর, row[c-1]=বাঁ
return row[n - 1]
# ---- tests ----
cases = [
([[1, 3, 1], [1, 5, 1], [4, 2, 1]], 7),
([[1, 2, 3], [4, 5, 6]], 12),
([[5]], 5),
([[1, 2, 3]], 6),
([[1], [2], [3]], 6),
([[1, 2], [1, 1]], 3),
]
for grid, want in cases:
assert min_path_memo(grid) == want, (grid, min_path_memo(grid))
assert min_path_tab(grid) == want, (grid, min_path_tab(grid))
assert min_path_row(grid) == want, (grid, min_path_row(grid))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `min_path_memo`: `cost(r,c)` cell `(r,c)` থেকে নিচ-ডান কোণে min cost দেয়; শেষ cell → নিজের cost, বাইরে → INF; `memo` repeated কাজ এড়ায়।
- `min_path_tab`: আগে প্রথম row আর প্রথম column running-sum দিয়ে ভরে নিই (ওদের একটাই দিক), তারপর ভেতরের cell-এ `grid + min(উপর, বাঁ)`; answer `dp[m-1][n-1]`।
- `min_path_row`: এক row রাখি; ভেতরের loop-এ `row[c]` তখনো পুরোনো (উপরের মান) আর `row[c-1]` নতুন (বাঁয়ের মান), তাই এক array-তেই কাজ হয়; প্রতি নতুন row-এ আগে `row[0]`-এ উপরের cost যোগ করি।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ ছয়টা grid আর সঠিক উত্তর — LeetCode-এর classic `7`, একটা `2×3`, আর তিনটা edge (single cell, single row, single column), শেষে একটা `2×2` যেখানে `min` সত্যিই কাজ করে (`3`)। প্রতিটার জন্য তিন function-ই মিলতে হবে। সব pass হলে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Grid DP (min); `dp[r][c] = grid[r][c] + min(উপর, বাঁ)`। Unique Paths-এর `+` এখানে `Math.min`।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// full 2D: প্রথম row/column running-sum, ভেতরে grid + min(উপর, বাঁ)
function minPathTab(grid) {
const m = grid.length, n = grid[0].length;
// প্রতিটা row আলাদা array (shared-ref এড়িয়ে)
const dp = Array.from({ length: m }, () => new Array(n).fill(0));
dp[0][0] = grid[0][0];
for (let c = 1; c < n; c++) dp[0][c] = dp[0][c - 1] + grid[0][c]; // প্রথম row
for (let r = 1; r < m; r++) dp[r][0] = dp[r - 1][0] + grid[r][0]; // প্রথম column
for (let r = 1; r < m; r++) {
for (let c = 1; c < n; c++) {
dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);
}
}
return dp[m - 1][n - 1];
}
// ---- test cases (example + edge) ----
const cases = [
[[[1, 3, 1], [1, 5, 1], [4, 2, 1]], 7],
[[[1, 2, 3], [4, 5, 6]], 12],
[[[5]], 5], // single cell
[[[1, 2, 3]], 6], // single row
[[[1], [2], [3]], 6], // single column
[[[1, 2], [1, 1]], 3],
];
for (const [grid, want] of cases) {
assert(minPathTab(grid) === want, "min " + JSON.stringify(grid));
}
console.log("সব JS test pass!");
```
> **JS টীকা:** 2D DP array বানাতে `Array.from({length: m}, () => new Array(n).fill(0))` — `new Array(m).fill(new Array(n))` সব row-কে এক reference করিয়ে দেয় (এক cell লিখলে সব row বদলায়)। প্রথম row/column-এ `Math.min` নয়, শুধু running-sum (সেখানে একটাই দিক); ভেতরের cell-এ `grid[r][c] + Math.min(...)`। `Math.min(a, b)` Python-এর `min`-এর সমতুল্য।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function minPathSum(grid: number[][]): number {
const m: number = grid.length, n: number = grid[0].length;
const dp: number[][] = Array.from({ length: m }, () => new Array