← All patternsGrid DP · template
Pattern · Dynamic Programming
Grid DP
Each cell's answer comes from the cells above and to the left; fill the grid row by row.
Time O(rows × cols) · Space O(rows × cols), or O(cols) with one row
Taught in Module 29: DP on Grids
Think of it like this
Counting routes through a city grid where you can only go right or down: each corner's count is the sum of the two corners leading into it.
Clues that point here
- → Paths on a grid moving right/down
- → Minimum path sum
- → Obstacles on a grid
- → Largest square of 1s
Not this pattern when
- ✕ Moves go in all four directions (graph search)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
int[][] dp = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (r == 0 && c == 0) dp[r][c] = grid[0][0];
else {
int up = r > 0 ? dp[r - 1][c] : Integer.MAX_VALUE;
int left = c > 0 ? dp[r][c - 1] : Integer.MAX_VALUE;
dp[r][c] = grid[r][c] + Math.min(up, left);
}
}
}
return dp[rows - 1][cols - 1];Common versions
- Unique paths
- Unique paths with obstacles
- Minimum path sum
- Maximal square
- Triangle
Practice problems with this pattern
29.1Unique PathsMediummain pattern29.2Unique Paths IIMediummain pattern29.3Minimum Path SumMediummain pattern29.4TriangleMediummain pattern29.5Minimum Falling Path SumMediummain pattern29.6Maximal SquareMediummain pattern29.7Dungeon GameHardmain pattern29.8Cherry Pickup IIHardmain pattern21.301 MatrixMediumalso uses it24.7Longest Increasing Path in a MatrixHardalso uses it