Minimum Path Sum
Find the cheapest top-left to bottom-right path in a grid moving only right or down, with a DP table where each cell takes the cheaper of above and left.
Problem Understanding
Minimum Path Sum: given an m × n grid of non-negative numbers, find a path from the top-left to the bottom-right corner that minimises the sum of the numbers along it. You may only move right or down.
Example: [[1,3,1],[1,5,1],[4,2,1]] returns 7, via 1 → 3 → 1 → 1 → 1.
The Intuition: Every Cell Has Two Doors
With moves restricted to right and down, the last step into any cell comes either from above or from the left. If you already know the cheapest cost to reach both of those, the cheapest way into this cell is its own cost plus the smaller one.
- The first row has only a left door; the first column only a top door.
- Fill the table row by row so both doors are always ready.
It is the same grid as Unique Paths, with min and costs instead of adding path counts, and the same row-by-row filling as Longest Common Subsequence.
Interactive Walkthrough
The costs are on the left and the dp table on the right. Each cell takes its cost plus the cheaper neighbour, which is tinted. At the end, the cheapest path turns green on both tables. Try Detour to see the path go the long way round an expensive middle row.
Dry Run Table
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
| dp | col 0 | col 1 | col 2 |
|---|---|---|---|
| row 0 | 1 | 4 | 5 |
| row 1 | 2 | 7 | 6 |
| row 2 | 6 | 8 | 7 |
For example, dp[1][1] = 5 + min(4, 2) = 7 and dp[2][2] = 1 + min(6, 8) = 7. Answer: 7.
The Solution Template
A full dp table filled row by row, with the edges handled first in each branch.
Minimum Path Sum Code
1var minPathSum = function(grid) {2 const m = grid.length, n = grid[0].length;3 const dp = Array.from({ length: m }, () => new Array(n).fill(0));4 for (let i = 0; i < m; i++) {5 for (let j = 0; j < n; j++) {6 if (i === 0 && j === 0) dp[i][j] = grid[0][0];7 else if (i === 0) dp[i][j] = dp[i][j - 1] + grid[i][j];8 else if (j === 0) dp[i][j] = dp[i - 1][j] + grid[i][j];9 else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];10 }11 }12 return dp[m - 1][n - 1];13};
Edge Cases & Common Mistakes
- A single row or column: there is only one path; the edge branches add it up.
- Treating the edges like inner cells:
dp[i − 1][j]does not exist on row 0; handle the first row and column separately. - Greedy choices: always stepping to the cheaper neighbour can walk into an expensive region later; only DP compares whole paths.
- Allowing diagonal or upward moves: changes the problem; with arbitrary moves you need Dijkstra.
- Space: one row of length n is enough:
dp[j] = grid[i][j] + min(dp[j], dp[j − 1]).
Summary
Each cell's cheapest cost is its own value plus the cheaper of the cell above and the cell to the left; the first row and column have only one way in. Fill the table row by row and return the bottom-right cell. O(m · n) time, O(m · n) or O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet