Easy Problemsminimizationgrid

Min Cost Path

Given a grid where every cell has a cost to enter, and starting at the top-left corner while moving only right or down at each step, find the minimum total cost to reach the bottom-right corner.

Do this lesson first: coin change

Example input

cost = [[1, 2, 3, 4], [1, 8, 2, 4], [9, 9, 1, 9], [5, 6, 5, 3]]

Expected output

17

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[r][c] = cost[r][c] + min(dp[r - 1][c], dp[r][c - 1])

Ask which step landed on (r, c). Only two are legal: down from (r - 1, c), or right from (r, c - 1). Whichever it was, the rest of that route has to be a cheapest route to that neighbour, which is the same question on a smaller corner of the grid, and the final step is charged cost[r][c] either way. So take the cheaper of the two neighbours and add this cell's cost once. It is a min rather than a sum because exactly one of the two steps actually happened. count-all-paths-in-a-grid asks about the same two neighbours and adds them instead, because there every route counts rather than competing.

dp[0][0] = cost[0][0], and that is a CONVENTION rather than something the statement forces. The statement says a cell has a cost to enter, and you never enter the cell you begin on, so a reading where the start is free is perfectly defensible; it just gives a different number at every size. This page charges for the start, because that is what almost every published version of the problem does, so a learner checking the answer against another source sees the same total. If you meet the other convention, subtract cost[0][0] from every cell. Row 0 has nothing above it and column 0 has nothing to its left, so those cells have one candidate instead of two and come out as running totals along the two edges. Filling row-major, left to right within each row, means the cell above and the cell to the left are both already final before any cell uses them, which is the only ordering property the recurrence needs.

Tabulation. Every cell lies on some route towards the corner, so there is no subproblem a top-down solve would get to skip, and memoization would only add call overhead to the same rows times cols cells. A cell reads the row above and its own left neighbour, so the table collapses to one rolling row of length cols once you trust it. Notice how little separates this page from count-all-paths-in-a-grid and paths-in-a-grid-with-obstacles: identical state, identical row-major sweep, identical two dependencies. Only the operator at the cell differs, a min plus this cell's cost here, a plain sum there, and a sum with blocked cells forced to zero in the obstacle version.

Time O(rows × cols)Space O(rows × cols), reducible to O(cols) with one rolling row

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0][0] = cost[0][0], and that is a CONVENTION rather than something the statement forces. The statement says a cell has a cost to enter, and you never enter the cell you begin on, so a reading where the start is free is perfectly defensible; it just gives a different number at every size. This page charges for the start, because that is what almost every published version of the problem does, so a learner checking the answer against another source sees the same total. If you meet the other convention, subtract cost[0][0] from every cell. Row 0 has nothing above it and column 0 has nothing to its left, so those cells have one candidate instead of two and come out as running totals along the two edges. Filling row-major, left to right within each row, means the cell above and the cell to the left are both already final before any cell uses them, which is the only ordering property the recurrence needs.

row r

0

1

2

3

0

1

3

6

10

1

2

10

8

12

2

11

19

9

18

3

16

22

14

17

column c: cheapest cost to reach (r, c)

min-cost-path.ts

1function minCost(cost) {
2 const n = cost.length, m = cost[0].length;
3 const dp = Array.from({ length: n }, () => new Array(m).fill(Infinity));
4 dp[0][0] = cost[0][0];
5 for (let r = 0; r < n; r++) {
6 for (let c = 0; c < m; c++) {
7 if (r === 0 && c === 0) continue;
8 const above = r > 0 ? dp[r - 1][c] : Infinity;
9 const left = c > 0 ? dp[r][c - 1] : Infinity;
10 dp[r][c] = cost[r][c] + Math.min(above, left);
11 }
12 }
13 return dp[n - 1][m - 1];
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

min-cost-path.ts

1function minCost(cost) {
2 const n = cost.length, m = cost[0].length;
3 const dp = Array.from({ length: n }, () => new Array(m).fill(Infinity));
4 dp[0][0] = cost[0][0];
5 for (let r = 0; r < n; r++) {
6 for (let c = 0; c < m; c++) {
7 if (r === 0 && c === 0) continue;
8 const above = r > 0 ? dp[r - 1][c] : Infinity;
9 const left = c > 0 ? dp[r][c - 1] : Infinity;
10 dp[r][c] = cost[r][c] + Math.min(above, left);
11 }
12 }
13 return dp[n - 1][m - 1];
14}

Where people go wrong

Stepping onto whichever neighbour is cheaper. From the start of this grid the cell below costs 1 and the cell to the right costs 2, so a greedy walk goes down, and that 1 is fenced in by an 8 and a 9: greedy pays 21 where the table pays 17. A cheap cell is worth nothing unless its neighbours are cheap too, which is precisely what a local rule cannot see and what the table prices for you. The second trap is the base. Decide out loud whether dp[0][0] is cost[0][0] or 0 before filling a single cell, because both conventions are in circulation and they disagree at every cell by exactly cost[0][0].

Allow diagonal moves as well as right and down.
A third candidate, dp[r - 1][c - 1], joins the min. State, sweep and order are untouched, since a row-major fill already has the diagonal neighbour final before it is used.
Maximize the total collected instead of minimizing the cost paid.
Swap min for max and change nothing else. That one word is the whole difference, exactly as the one word between this page and count-all-paths-in-a-grid is min against sum.
Allow moves in all four directions, not just right and down.
The table stops working, and it is worth knowing why: with left and up allowed, dp[r][c] can depend on cells the sweep has not reached yet, so no fill order is safe. There is no longer a last decision that shrinks the problem, and you need Dijkstra over the grid instead.

House Robber Decode Ways