Advanced · Module 18 · Lesson 5
Grid DP
Paths, costs, obstacles, and multidirectional transitions.
Lesson 109 of 123
1d streakGrid DP: 2D Coordinate Transitions & 1D Space Optimization
In grid dynamic programming problems (Unique Paths, Minimum Path Sum, Cherry Pickup), movements are typically restricted to down (r + 1, c) and right (r, c + 1). Every cell (r, c) depends strictly on its immediate neighbors: top (r - 1, c) and left (r, c - 1). While a naive matrix allocates O(M × N) auxiliary space, observing that row r depends only on row r and row r - 1 allows compressing the space to a single 1D array of size O(N).
Architectural Boundary · Do Not Confuse
2D DP Matrix: O(M × N) Space
1D Rolling Array: O(N) Space
A 2D matrix stores all historical rows. A 1D rolling array updates in place: dp[c] before the update holds the top value dp[r-1][c], while dp[c-1] holds the newly updated left value dp[r][c-1].
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
// Initialize starting cell
dp[0] = grid[0][0];
// Initialize first row (can only arrive from the left)
for (int c = 1; c < n; c++) {
dp[c] = dp[c - 1] + grid[0][c];
}
// Process remaining rows
for (int r = 1; r < m; r++) {
dp[0] += grid[r][0]; // First column can only arrive from above
for (int c = 1; c < n; c++) {
// dp[c] is current top, dp[c-1] is newly computed left
dp[c] = Math.min(dp[c], dp[c - 1]) + grid[r][c];
}
}
return dp[n - 1];
}Active Recall Checkpoint
Why can Minimum Path Sum be solved in O(N) space instead of O(M × N)?
Show answer & explanation
Because the recurrence relation dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]) only references the current row and the row immediately above it. Historical rows prior to r-1 are never read again.
Use it when
Use Grid DP for shortest/cheapest path across matrices with unidirectional moves (down/right), obstacle navigation, and counting distinct paths.
Reconsider when
Reconsider when movement is allowed in all four directions (up/down/left/right) with cycles; use Dijkstra’s algorithm or 0-1 BFS instead.
Cost Model
Complexity & Trade-offs
When to use it
- Optimization, counting, and feasibility with overlapping subproblems.
- Sequence, grid, interval, tree, subset, and digit constraints.
- Replacing exponential recursion with reusable state.
Common mistakes
- Defining a state that lacks information needed by the transition.
- Iterating in an order that reads unresolved or same-round values.
- Optimizing space before proving dependencies.
Practice prompts
- Reproduce the worked Grid DP example without looking at the trace.
- Change one input condition and explain whether the Grid DP invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check