2D DP
Same grid, minimize sum
Why it matters
Logistics grids, image seam carving, and game maps assign a cost to each position and need the cheapest route through them. Enumerating every right-and-down route repeats the same remaining regions exponentially. The exact minimum must be found in one pass over the grid without allocating another full table.
Example
Minimum Path Sum
Walk from top-left to bottom-right, moving only down or right. Return the minimum sum of numbers along a path.
- Input
- grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
- Output
- 7
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Minimum Path Sum
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]→7
The baseline, Try every path recursively, is O(2^(m + n)) · O(m + n). The better model below keeps this exact input and removes that bottleneck.
For [[1, 3, 1], [1, 5, 1], [4, 2, 1]], brute recursion explores every route and recomputes shared cells. Store the cheapest total directly in each cell; the bottom-right becomes 7 without a second table.
In [[1, 3, 1], [1, 5, 1], [4, 2, 1]], leave the start as 1. The top row accumulates to [1, 4, 5], and the left column accumulates to [1, 2, 6] because edge cells have only one way in.
At the center, add its cost 5 to min(4 above, 2 left) to store 7. The remaining totals make the grid [[1, 4, 5], [2, 7, 6], [6, 8, 7]]. Overwriting works because each cell reads only completed totals above and left.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.