Skip to content
← All Patterns
← Greedy
Dynamic ProgrammingIntermediate

Matrix / Grid DP

Fill a 2D DP table where each cell represents the optimal answer for reaching that position in a grid, using values from adjacent cells.

Problem: Minimum Path Sum (Grid DP)

Find the path from top-left to bottom-right that minimizes the total sum. You can only move right or down.

Grid

1
3
1
2
1
5
1
3
4
2
1
1

DP Table

1
?
?
?
?
?
?
?
?
?
?
?

dp[0][0] = 1 (start)

Initialize: the cost to reach (0,0) is just its own value, 1.

Step 1/13
Speed:

When to Use

  • Find min/max cost path in a grid
  • Count unique paths with obstacles
  • Grid-based optimization (dungeon game, cherry pickup)
  • 2D space where each cell depends on neighbors

Key Indicators

  • dp[i][j] depends on dp[i-1][j] and dp[i][j-1]
  • Grid/matrix traversal with accumulation
  • Min/max path cost
  • Count paths from top-left to bottom-right

Complexity

Time

O(m × n)

Space

O(m × n), optimizable to O(n)

Common Problems

Unique PathsMinimum Path SumDungeon GameMaximal SquareCherry Pickup

Code

# Minimum path sum in grid
dp = copy of grid
for i in range(rows):
    for j in range(cols):
        if i == 0 and j == 0: continue
        from_top = dp[i-1][j] if i > 0 else infinity
        from_left = dp[i][j-1] if j > 0 else infinity
        dp[i][j] += min(from_top, from_left)
return dp[rows-1][cols-1]

Want all 29 patterns with detailed visual walkthroughs?

The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.

Book Coming Soon ($4.99)