BeginnerDynamic Programming

2D Grid DP

DP on grids for counting paths, minimal costs, and shapes

Time: O(RC)
Space: O(RC) or O(C)
Pattern Overview

Core Idea

dp[r][c] depends on neighbors (up/left/diag) under constraints, often with obstacles.

When to Use

Use for path counting, minimal path sum, or maximal shape areas in grids.

General Recognition Cues
General indicators that this pattern might be applicable
  • Grid with moves
  • Obstacles
  • Accumulating cost
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Unique Paths

Count routes with allowed moves

When to Use This Variant
  • Right/down
Use Case
Counts
Advantages
  • Simple recurrence
Implementation
def unique_paths(m, n):
    dp=[[1]*n for _ in range(m)]
    for i in range(1,m):
        for j in range(1,n): dp[i][j]=dp[i-1][j]+dp[i][j-1]
    return dp[m-1][n-1]
2

Min Cost Path

Accumulate minimal sum to cell

When to Use This Variant
  • Weights
Use Case
Minimal path sum
Advantages
  • O(RC)
Implementation
def min_path_sum(grid):
    R,C=len(grid),len(grid[0]); dp=[[0]*C for _ in range(R)]
    dp[0][0]=grid[0][0]
    for i in range(1,R): dp[i][0]=dp[i-1][0]+grid[i][0]
    for j in range(1,C): dp[0][j]=dp[0][j-1]+grid[0][j]
    for i in range(1,R):
        for j in range(1,C): dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1])
    return dp[R-1][C-1]
3

Shapes

DP for squares/rectangles of ones

When to Use This Variant
  • Maximal square
Use Case
Largest area
Advantages
  • Local transitions
Implementation
def maximal_square(matrix):
    R,C=len(matrix),len(matrix[0]); dp=[[0]*C for _ in range(R)]; best=0
    for i in range(R):
        for j in range(C):
            if matrix[i][j]=='1':
                dp[i][j]=1 if i==0 or j==0 else 1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
                best=max(best, dp[i][j])
    return best*best
Common Pitfalls
Watch out for these common mistakes
  • Bounds checks
  • Initialization of first row/col
  • Obstacle handling
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(RC)

Visit each cell.

Space Complexity
O(RC) or O(C)

Row compression often possible.

Ready to test your knowledge?

Test your pattern recognition with interactive questions