Min Cost Path in a Grid

You are given a grid cost with m rows and n columns. cost[i][j] is a non-negative number — the price of stepping onto cell (i, j).

Start at the top-left cell (0, 0) and finish at the bottom-right cell (m − 1, n − 1). From any cell (i, j) you may move one step right to (i, j + 1) or one step down to (i + 1, j) — never up, left, or diagonally.

The total cost of a path is the sum of cost[i][j] over every cell on it (including both the start and the end). Find the minimum total cost.

Tiny example. For

the path (0,0) → (0,1) → (0,2) → (1,2) → (2,2) pays 1 + 3 + 1 + 1 + 1 = 7, which is the minimum.

Meaning of the state. Let dp(i, j) = minimum total cost of any path from (0, 0) to (i, j).

Idea in words. To reach (i, j) your last move came from either (i − 1, j) (moved down) or (i, j − 1) (moved right). The path before that last move was itself a path from (0, 0) to that previous cell — and if dp(i, j) is to be minimum, that earlier path must also be minimum. So:

for every cell (i, j) with i ≥ 1 and j ≥ 1. Cells in the first row or first column have only one way in (the other neighbour is off the grid), so they use a simpler rule — see the base cases.

Why this is correct. Any optimal path to (i, j) ends with one of the two moves; the cheaper of those two predecessor paths plus cost[i][j] beats any other plan. Trying both options covers every legal way to arrive.

Use a 2D table memo[0…m−1][0…n−1] with a sentinel like −1 for “not computed yet.” When asked for dp(i, j):

• If memo[i][j] is set, return it.
• Otherwise compute it from the recurrence (recursing on (i − 1, j) and (i, j − 1)), store the result in memo[i][j], and return.

There are m · n states, each does O(1) extra work after its two recursive calls, so total work is O(m · n) time and O(m · n) space. Recursion depth is at most m + n (any path is that many steps).

The recurrence assumes both neighbours exist. For the edges of the grid only one neighbour is real:

Explanation. From (0, 0) you cannot have moved at all, so the cost is just cost[0][0]. In the top row you can only have come from the left; in the left column only from above. Every recursion eventually reaches (0, 0) because each step strictly decreases i + j.

Take the 3 × 3 grid from the Problem section:

Fill dp row by row, then column by column inside each row.

Row 0 (top row, only “from left”):

• dp(0, 0) = 1
• dp(0, 1) = dp(0, 0) + 3 = 4
• dp(0, 2) = dp(0, 1) + 1 = 5

Column 0 (left column, only “from above”):

• dp(1, 0) = dp(0, 0) + 1 = 2
• dp(2, 0) = dp(1, 0) + 4 = 6

Inside cells use the full recurrence:

• dp(1, 1) = 5 + min(dp(0, 1), dp(1, 0)) = 5 + min(4, 2) = 7
• dp(1, 2) = 1 + min(dp(0, 2), dp(1, 1)) = 1 + min(5, 7) = 6
• dp(2, 1) = 2 + min(dp(1, 1), dp(2, 0)) = 2 + min(7, 6) = 8
• dp(2, 2) = 1 + min(dp(1, 2), dp(2, 1)) = 1 + min(6, 8) = 7

The answer is dp(2, 2) = 7 — matching the path (0,0) → (0,1) → (0,2) → (1,2) → (2,2).

Read MIN-COST(i, j) as a question: “what is the cheapest way to reach cell (i, j)?” It answers by asking the same question about the cell above and the cell to the left, takes the cheaper of the two, and adds this cell's own cost. The memo table makes sure each cell is solved only once.

Time: O(m · n) — each of the m · n states does constant extra work. Space: O(m · n) for the memo table; recursion depth is at most m + n.