Dynamic Programming on 2D grids is one of the most popular DP patterns. Many real-world problems like pathfinding, robot navigation, game boards, obstacle courses, and resource collection can be mapped into grid-based DP problems.
The key idea:
- Imagine you are on a grid (like a chessboard).
- At each cell, you make decisions (move right, move down, sometimes diagonally).
- The DP state keeps track of the best solution up to that cell (minimum cost, maximum coins, number of ways, etc.).
- By filling the grid step by step, you solve the entire problem.
🔑 Core Concepts for Grid DP
-
State → What does
dp[i][j]mean?
- It usually represents the "best" (or number of ways, or cost) to reach cell
(i, j).
-
Transition → How do we reach
dp[i][j]?
- Common moves: from top
(i-1, j)or left(i, j-1), sometimes diagonally.
Base Cases → Usually the starting cell
(0,0)is initialized (like starting point of a robot).Answer → Usually found at
dp[m-1][n-1](bottom-right cell).
🧩 Example 1: Unique Paths (Count All Ways)
Problem: A robot can only move right or down on an m x n grid. How many unique paths are there to reach the bottom-right corner?
Approach:
- If you’re at
(i, j), you could only have come from above(i-1, j)or left(i, j-1). - Add those ways together.
Code:
public class UniquePaths {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// Initialize first row and first column (only 1 way to move straight)
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
// Fill rest of grid
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
🧩 Example 2: Unique Paths with Obstacles
Problem: Same as above, but some cells are blocked (1 = obstacle).
Approach:
- If there’s an obstacle, set
dp[i][j] = 0. - Otherwise, sum up paths from top and left.
Code:
public class UniquePathsWithObstacles {
public int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
// If starting point is blocked → no path
if (grid[0][0] == 1) return 0;
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) { // obstacle
dp[i][j] = 0;
} else {
if (i > 0) dp[i][j] += dp[i-1][j];
if (j > 0) dp[i][j] += dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
🧩 Example 3: Minimum Path Sum
Problem: Each cell has a cost. Find the minimum cost to reach the bottom-right.
Approach:
- At
(i, j), take the minimum of coming from top or left, plus the current cell’s cost.
Code:
public class MinPathSum {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// First row
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
// First column
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
🧩 Example 4: Maximum Path Sum (Collecting Maximum Coins)
Problem: Each cell has some coins. Collect the maximum coins while moving from top-left to bottom-right.
Approach:
- Same as minimum path sum, but take the maximum instead of minimum.
Code:
public class MaxPathSum {
public int maxPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
🧩 Example 5: Minimum Falling Path Sum (Diagonal Allowed)
Problem: From the top row, move down to the last row. At each step, you can go down, down-left, or down-right. Find the minimum path sum.
Approach:
- Each cell depends on three possible parents.
Code:
public class MinFallingPathSum {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int[][] dp = new int[n][n];
// Copy first row
for (int j = 0; j < n; j++) dp[0][j] = matrix[0][j];
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minPrev = dp[i-1][j];
if (j > 0) minPrev = Math.min(minPrev, dp[i-1][j-1]);
if (j < n-1) minPrev = Math.min(minPrev, dp[i-1][j+1]);
dp[i][j] = matrix[i][j] + minPrev;
}
}
int ans = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) ans = Math.min(ans, dp[n-1][j]);
return ans;
}
}
🧩 Example 6: Cherry Pickup (Two Robots Collecting Maximum)
Problem: Two robots start at (0,0) and (0, n-1) and move down to the last row. Each cell has cherries. If both robots pick from the same cell, count it once. Find maximum cherries collected.
Approach:
- State →
(row, col1, col2)(row number and positions of both robots). - Transition → Robots move in 9 combinations (left, down, right).
Code (recursive + memoization):
public class CherryPickup {
int[][][] memo;
public int cherryPickup(int[][] grid) {
int m = grid.length, n = grid[0].length;
memo = new int[m][n][n];
for (int[][] layer : memo)
for (int[] row : layer)
Arrays.fill(row, -1);
return dfs(grid, 0, 0, n-1);
}
private int dfs(int[][] grid, int row, int col1, int col2) {
int m = grid.length, n = grid[0].length;
if (col1 < 0 || col1 >= n || col2 < 0 || col2 >= n) return 0;
if (row == m) return 0;
if (memo[row][col1][col2] != -1) return memo[row][col1][col2];
int cherries = grid[row][col1];
if (col1 != col2) cherries += grid[row][col2];
int max = 0;
for (int d1 = -1; d1 <= 1; d1++) {
for (int d2 = -1; d2 <= 1; d2++) {
max = Math.max(max, dfs(grid, row+1, col1+d1, col2+d2));
}
}
return memo[row][col1][col2] = cherries + max;
}
}
🔥 Key Takeaways
- Grid DP is about building solutions cell by cell.
- Always think → “How can I reach this cell?” (from top, left, diagonal, or multiple agents).
- Base cases: first row/col, or blocked cells.
- Space optimization → Instead of full
dp[][], you can use 1D arrays if only previous row/column is needed. - Applications go beyond games → logistics, robotics, shortest/cheapest route problems, even AI pathfinding.
Top comments (0)