DP on Grids
Grid-based DP problems are common, e.g., minimum path sum, unique paths, and grid traveling. They are often solved with 2D DP tables.
Example: Minimum Path Sum
Given a grid filled with non-negative numbers, find a path from top-left to bottom-right that minimizes the sum of numbers along the path (only move right or down).
DP recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) with base case dp[0][0] = grid[0][0].
Java implementation:
public static int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][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++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
Other grid DP problems: unique paths, coin change on grid, cherry pickup, etc.
Two Minute Drill
- Grid DP often uses 2D table with base cases for first row/column.
- Transitions depend on movement constraints (right/down, etc.).
- Can often optimize space to 1D array when only previous row is needed.
- Used in robotics, pathfinding, and game theory.
Need more clarification?
Drop us an email at career@quipoinfotech.com