DP on Grids
In this page:
Grid DP Idea
Grid DP problems ask something about paths through a 2D grid — the number of ways to reach a cell, or the cheapest path to it — and solve it by filling in an answer for every cell based on the cells that can reach it.
Example: Grid DP Idea
#include <iostream>
using namespace std;
int main() {
cout << "Grid DP: fill in an answer for every cell based on the cells that can reach it";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Grid DP: fill in an answer for every cell based on the cells that can reach it");
}
}print("Grid DP: fill in an answer for every cell based on the cells that can reach it")#include <stdio.h>
int main() {
printf("Grid DP: fill in an answer for every cell based on the cells that can reach it");
return 0;
}Login to try C/C++/Java code in the editor
State
dp[r][c] stores the answer for the cell at row r, column c, so the grid of dp values mirrors the shape of the original grid, with each cell's answer built from cells computed earlier.
Example: State
#include <iostream>
using namespace std;
int main() {
int dp[3][3] = {0};
cout << "dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] dp = new int[3][3];
System.out.println("dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape");
}
}dp = [[0]*3 for _ in range(3)]
print("dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape")#include <stdio.h>
int main() {
int dp[3][3] = {0};
printf("dp[r][c] holds the answer for row r, column c -- the dp grid mirrors the original grid's shape");
return 0;
}Login to try C/C++/Java code in the editor
Transition
When movement is restricted to right and down, a cell can only be reached from the cell directly above it or the cell directly to its left, so dp[r][c] is typically built by combining dp[r-1][c] and dp[r][c-1] in whatever way the problem asks (sum for counting paths, minimum for cheapest path).
Example: Transition
#include <iostream>
using namespace std;
int main() {
int dp[3][3] = {0};
dp[0][0] = 1;
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++) {
if (r > 0) dp[r][c] += dp[r-1][c];
if (c > 0) dp[r][c] += dp[r][c-1];
}
cout << "Paths to bottom-right (right/down moves only): " << dp[2][2];
return 0;
}public class Main {
public static void main(String[] args) {
int[][] dp = new int[3][3];
dp[0][0] = 1;
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++) {
if (r > 0) dp[r][c] += dp[r-1][c];
if (c > 0) dp[r][c] += dp[r][c-1];
}
System.out.println("Paths to bottom-right (right/down moves only): " + dp[2][2]);
}
}dp = [[0]*3 for _ in range(3)]
dp[0][0] = 1
for r in range(3):
for c in range(3):
if r > 0: dp[r][c] += dp[r-1][c]
if c > 0: dp[r][c] += dp[r][c-1]
print("Paths to bottom-right (right/down moves only):", dp[2][2])#include <stdio.h>
int main() {
int dp[3][3] = {0};
dp[0][0] = 1;
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++) {
if (r > 0) dp[r][c] += dp[r-1][c];
if (c > 0) dp[r][c] += dp[r][c-1];
}
printf("Paths to bottom-right (right/down moves only): %d", dp[2][2]);
return 0;
}Login to try C/C++/Java code in the editor
Minimum Path Sum
For a minimum path sum problem, dp[r][c] equals the cell's own cost plus whichever of the top or left neighbor has the smaller accumulated cost so far, propagating the cheapest route forward one cell at a time.
Example: Minimum Path Sum
#include <iostream>
using namespace std;
int main() {
int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
int dp[3][3];
dp[0][0] = grid[0][0];
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++) {
if (r==0 && c==0) continue;
int top = r>0 ? dp[r-1][c] : 1000000;
int left = c>0 ? dp[r][c-1] : 1000000;
dp[r][c] = grid[r][c] + min(top, left);
}
cout << "Minimum path sum: " << dp[2][2];
return 0;
}public class Main {
public static void main(String[] args) {
int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
int[][] dp = new int[3][3];
dp[0][0] = grid[0][0];
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++) {
if (r==0 && c==0) continue;
int top = r>0 ? dp[r-1][c] : 1000000;
int left = c>0 ? dp[r][c-1] : 1000000;
dp[r][c] = grid[r][c] + Math.min(top, left);
}
System.out.println("Minimum path sum: " + dp[2][2]);
}
}grid = [[1,3,1],[1,5,1],[4,2,1]]
dp = [[0]*3 for _ in range(3)]
dp[0][0] = grid[0][0]
for r in range(3):
for c in range(3):
if r == 0 and c == 0:
continue
top = dp[r-1][c] if r > 0 else float('inf')
left = dp[r][c-1] if c > 0 else float('inf')
dp[r][c] = grid[r][c] + min(top, left)
print("Minimum path sum:", dp[2][2])#include <stdio.h>
int main() {
int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
int dp[3][3];
dp[0][0] = grid[0][0];
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++) {
if (r==0 && c==0) continue;
int top = r>0 ? dp[r-1][c] : 1000000;
int left = c>0 ? dp[r][c-1] : 1000000;
dp[r][c] = grid[r][c] + (top < left ? top : left);
}
printf("Minimum path sum: %d", dp[2][2]);
return 0;
}Login to try C/C++/Java code in the editor
Practice
This pattern extends naturally to grids with obstacles (blocked cells simply contribute zero ways or infinite cost) and is a common way to model constrained movement problems like robot navigation.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation");
}
}print("Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation")#include <stdio.h>
int main() {
printf("Extends to grids with obstacles (blocked cells contribute 0 ways / infinite cost) for robot navigation");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: