009 — Minimum Path Sum

Source

• Original source: Classic grid cost-minimization DP exercise
• Platform: LeetCode — https://leetcode.com/problems/minimum-path-sum/
• Topic: dynamic programming
• Difficulty: Medium
• Pattern: Grid DP (min)
• Basic idea inherited from: #7 Unique Paths — একই right/down grid, কিন্তু +-কে min দিয়ে বদলানো

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 করো।

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]

সবচেয়ে সস্তা path: 1 -> 3 -> 1 -> 1 -> 1 = 7

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।

6. Real-life analogy

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

7. Visual explanation

dp[r][c] = start থেকে (r,c) পর্যন্ত min cost। উপরের grid:

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।

8. Example input and output

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, পুরোটা যোগ)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা cell থেকে recurse করে দুই দিকের min path খোঁজা — ডানে যাও আর নিচে যাও, যেটা কম।

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:

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-তে বারবার লাগবে।

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। ✔

15. Python solution

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 যোগ করি।

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!।

18. Time complexity

• Memoization ও tabulation: O(m·n) — প্রতিটা cell একবার করে।
• Row version: O(m·n) time, কিন্তু কম space।

(Naive recursion ছিল প্রায় O(2^(m+n))।)

19. Space complexity

• Memoization: O(m·n) — dict + recursion stack।
• Full tabulation: O(m·n) — 2D array।
• Row version: O(n) — এক row।

20. Common mistakes

• প্রথম row/column-এ min ব্যবহার করা — ওখানে দুটো দিক নেই, একটাই (running sum); ভুল করে min নিলে out-of-bound বা 0 মিশে যায়।
• নিজের cell-এর cost grid[r][c] যোগ করতে ভুলে যাওয়া — তখন শুধু পথের সংখ্যা গোনার মতো হয়ে যায়, cost নয়।
• row-rolling version-এ নতুন row শুরু করার সময় row[0]-তে উপরের cost যোগ না করা — column 0 ভুল হয়ে যায়, কারণ সেখানে বাঁ neighbor নেই।

21. Which basic problem this inherits from

ভিত্তি: #7 Unique Paths-এর right/down grid DP, যোগকে min দিয়ে বদলানো — যেমন #3 #2 থেকে এসেছিল। ../state-transition-thinking.md-এর "Problem 4 — Grid Paths" section-এ fill-order-এর geometry আছে; ../patterns.md-এর "Grid DP" family-ও এখানে।

22. Similar harder problems

• Minimum Falling Path Sum (তিন দিক থেকে আসা যায়) — https://leetcode.com/problems/minimum-falling-path-sum/
• Triangle (ত্রিভুজ-আকৃতির grid-এ min path) — https://leetcode.com/problems/triangle/
• Dungeon Game (পেছন থেকে min health track) — https://leetcode.com/problems/dungeon-game/

23. Pattern learned

Grid DP (min): state দুটো index (r, c), transition grid[r][c] + min(উপর, বাঁ), fill order row-by-row বাঁ-থেকে-ডান (transition arrow-এর geometry থেকেই বেরোয়)। শুধু আগের row লাগে বলে O(n) space-এ নামে। Counting grid-এর +-কে min-এ বদলালেই optimization grid — এই operator-swap বহু জোড়া problem জুড়ে দেয়।

24. Final summary

ভবিষ্যতের আমাকে: "Minimum Path Sum = Unique Paths, কিন্তু +-এর জায়গায় min।" State dp[r][c] = (r,c)-তে পৌঁছানোর min cost, transition dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]), base প্রথম row/column running-sum। মনে রেখো: প্রথম row/column-এ min নয়, শুধু যোগ; আর এক row-তে compress করা যায়।

25. JavaScript solution (with test cases)

Grid DP (min); dp[r][c] = grid[r][c] + min(উপর, বাঁ)। Unique Paths-এর + এখানে Math.min।

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-এর সমতুল্য।

26. TypeScript solution (with test cases)

function minPathSum(grid: number[][]): number {
  const m: number = grid.length, n: number = grid[0].length;
  const dp: number[][] = Array.from({ length: m }, () => new Array<number>(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];
  for (let r = 1; r < m; r++) dp[r][0] = dp[r - 1][0] + grid[r][0];
  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];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number[][], number]> = [
  [[[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],
];
for (const [grid, want] of cases) expect(minPathSum(grid), want, "min");
console.log("সব TS test pass!");

TS টীকা: grid: number[][] ও dp: number[][] typing দিয়ে দুটোই number-এর 2D array তে locked; new Array<number>(n) element-type স্পষ্ট করে। cases: Array<[number[][], number]> tuple-type প্রতিটা case-এ [grid, expected] জোড়া নিশ্চিত করে — ভুল আকৃতির input compile-time-এ ধরা পড়ে।

27. কোথায় কাজে লাগে (real-world use)

• Least-cost grid routing: প্রতিটা cell-এ cost থাকা map-এ (terrain/toll) এক কোণ থেকে আরেক কোণে সবচেয়ে সস্তা পথ।
• Image seam carving: ছবিতে সবচেয়ে কম-energy উল্লম্ব/অনুভূমিক seam বের করে content-aware resize।
• Robot / drone energy path: weighted grid-এ সবচেয়ে কম শক্তি-খরচের গতিপথ পরিকল্পনা।
• DNA / sequence scoring grid: dynamic-programming alignment-এর min-cost cell-traversal (এই grid-skeleton-এর আত্মীয়)।
• Pipeline / assembly cost: stage-grid-এ সবচেয়ে কম মোট খরচের route বাছা।

মূল pattern: counting grid-এর +-কে min দিয়ে বদলালেই optimization grid; transition grid[r][c] + min(উপর, বাঁ), O(n) space-এ নামে।

---

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