Minimum Path Sum
Problem Statement
You are given an m x n grid filled with non-negative numbers. Starting at the top-left cell, move only down or right until you reach the bottom-right cell. Return the minimum possible sum of values along the path, including both endpoints.
Input
A 2D integer grid grid containing non-negative cell costs.
Output
An integer: the minimum path sum from the top-left cell to the bottom-right cell.
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 <= m, n <= 200 - •
0 <= grid[i][j] <= 200
Examples
Example 1
grid = [[1,3,1],[1,5,1],[4,2,1]]
7Example 2
grid = [[1,2,3],[4,5,6]]
12Learning Objectives
- Convert a grid path problem from counting paths to minimising accumulated cost.
- Define each state as the best cost to reach a cell from the start.
- Handle first-row and first-column base cases as forced paths.
- Compress the table to a 1D row while preserving top and left dependencies.
Intuition
The robot still reaches each cell from only two possible neighbours: top or left. The difference from Unique Paths is the value we store. Instead of asking how many ways reach this cell, ask what is the cheapest total cost to reach this cell.
If the cheapest path into the top neighbour is known and the cheapest path into the left neighbour is known, then the cheapest path into the current cell must take the smaller of those two and add the current cell cost. Non-negative costs are not even essential for this recurrence; the acyclic movement direction is what makes the local choice safe.
For a 1D row, best[col] before the update is the cheapest cost from above, and best[col - 1] after its update is the cheapest cost from the left. Taking their minimum gives the best predecessor.
Common mistakes
- ×Using addition of top and left as in path counting instead of taking the minimum.
- ×Forgetting to add the current grid value after choosing the cheaper predecessor.
- ×Initialising edge cells to zero instead of the cumulative forced path cost.
- ×Updating the first column with a minimum even though it can only come from above.
- ×Treating the problem as general shortest path even though the movement direction makes DP sufficient.
State Definition
Let dp[i][j] be the minimum path sum needed to reach cell (i, j) from (0, 0) using only down and right moves. The answer is dp[m - 1][n - 1].
In the 1D version, best[j] stores the minimum path sum to reach column j in the current row after it has been processed.
State Transition
Base case: dp[0][0] = grid[0][0]. Cells in the first row can only come from the left, and cells in the first column can only come from above.
For every inner cell:
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
In the 1D version, update best[j] = grid[i][j] + min(best[j], best[j - 1]), where the old best[j] is the top neighbour and best[j - 1] is the current-row left neighbour.
Solutions
Solution: Space-optimized row DP
Keep one row of best costs. Build the first row as cumulative sums, then process each later row left to right using the smaller of the top and left costs.
Step-by-step
- Set best[0] to the starting cell cost.
- Fill the first row by cumulative addition because only right moves are possible there.
- For each new row, update best[0] by adding the first-column cost because only down moves are possible.
- For each inner column, add the current grid value to the smaller of best[col] from above and best[col - 1] from the left.
- Return best[cols - 1].
O(m · n)
O(n)
The algorithm visits each cell once and stores one row of minimum costs.
Java implementation
Dry Run
Sample input
grid = [[1,3,1],[1,5,1],[4,2,1]]. First initialise the top row as cumulative costs.
| step | cell cost | top cost | left cost | best after update |
|---|---|---|---|---|
| top row | 1, 3, 1 | - | forced | [1,4,5] |
| (1,0) | 1 | 1 | none | [2,4,5] |
| (1,1) | 5 | 4 | 2 | [2,7,5] |
| (1,2) | 1 | 5 | 7 | [2,7,6] |
| (2,0) | 4 | 2 | none | [6,7,6] |
| (2,1) | 2 | 7 | 6 | [6,8,6] |
| (2,2) | 1 | 6 | 8 | [6,8,7] |
The bottom-right value becomes 7, matching the path 1 -> 3 -> 1 -> 1 -> 1. Each inner update chooses the cheaper predecessor, then pays the current cell cost.
Complexity Analysis
The row-array solution is optimal for this DP dependency pattern: O(m · n) time to inspect all costs and O(n) auxiliary space for the previous row.
Space-optimized row DP
O(m · n)
O(n)
The algorithm visits each cell once and stores one row of minimum costs.
Interview Tips
Make the contrast with Unique Paths explicit: the structure is identical, but the aggregation changes from sum to minimum plus current cost. Interviewers like to see that you can reuse the grid-DP template while swapping the meaning of the state.
Likely follow-ups
- How would you reconstruct one minimum-cost path after computing the cost?
- What if some cells are blocked and cannot be used?
- What if movement were allowed in four directions instead of only down and right?
- Can you modify the solution when the grid is streamed row by row?
Similar Problems
Key Takeaways
- Minimum path grid DP stores the best cost to reach each cell.
- The transition uses current cost plus the cheaper of top and left.
- Edge cells are forced paths and must be initialised cumulatively.
- The previous-row dependency compresses naturally to O(n) space.