Grid DP

Grid DP: Finding Your Way Through a Magical Maze 🏰

The Adventure Begins

Imagine you have a treasure map. The map shows a grid of rooms in an ancient castle. You start at the top-left corner and need to reach the treasure in the bottom-right corner. But here’s the catch: you can only walk RIGHT or DOWN. No going backwards!

This is Grid DP - one of the most beautiful patterns in Dynamic Programming. It’s like solving a maze by remembering every path you’ve already explored.

What is DP on Grids?

Think of a grid like a checkerboard or a chocolate bar divided into squares.

Start → [S][ ][ ]
        [ ][ ][ ]
        [ ][ ][T] ← Treasure!

The Big Idea: Instead of trying ALL possible paths (which takes forever), we solve smaller pieces first, then build up to the answer.

Why Does This Work?

Imagine you’re at any square in the grid. You could have arrived from:

• The square above you (came DOWN)
• The square to your left (came RIGHT)

That’s it! Just two possibilities. This makes our life easy.

Simple Analogy: It’s like counting how many ways you can walk from your bedroom to the kitchen if you can only go through certain doorways. You count room by room until you reach the kitchen.

Unique Paths: Counting Every Possible Route

The Story

A little robot lives in the top-left corner of a grid. It wants to reach the bottom-right corner. The robot can only move right or down. How many different paths can it take?

Example: 3×3 Grid

Robot → [R][ ][ ]
        [ ][ ][ ]
        [ ][ ][G] ← Goal

Let’s count step by step:

Step 1: Fill the first row. There’s only ONE way to reach any cell in the first row - keep going right!

[1][1][1]
[ ][ ][ ]
[ ][ ][ ]

Step 2: Fill the first column. Only ONE way to reach any cell in the first column - keep going down!

[1][1][1]
[1][ ][ ]
[1][ ][ ]

Step 3: For every other cell, add the ways from above + left:

[1][1][1]
[1][2][3]
[1][3][6]

Answer: 6 paths!

The Magic Formula

// For any cell (i, j):
dp[i][j] = dp[i-1][j] + dp[i][j-1]

Translation: Ways to reach me = Ways to reach the cell above + Ways to reach the cell on my left.

Java Code

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    // First row: only one way
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }

    // First column: only one way
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }

    // Fill the rest
    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];
}

Visual Journey

graph TD
    A["Start #40;0,0#41;"] --> B["Only Right →"]
    A --> C["Only Down ↓"]
    B --> D["Fill Row 1"]
    C --> E["Fill Column 1"]
    D --> F["Fill Inside"]
    E --> F
    F --> G["Answer at Bottom-Right!"]

Minimum Path Sum: Finding the Cheapest Route

The Story

Now our grid isn’t empty! Each room has a toll - a number of gold coins you must pay to pass through. We want to find the path that costs the least gold from start to finish.

Example

[1][3][1]
[1][5][1]
[4][2][1]

Goal: Find the path with smallest total cost.

Step-by-Step Solution

Start: We begin at top-left. Cost to reach here = 1 (just this cell).

[1][ ][ ]
[ ][ ][ ]
[ ][ ][ ]

First Row: Can only come from the left.

[1][4][5]     ← 1, then 1+3=4, then 4+1=5
[ ][ ][ ]
[ ][ ][ ]

First Column: Can only come from above.

[1][4][5]
[2][ ][ ]     ← 1+1=2
[6][ ][ ]     ← 2+4=6

Fill the Rest: Pick the MINIMUM of (above, left) and add current cell.

[1][4][5]
[2][7][6]     ← min(4,2)+5=7, min(5,7)+1=6
[6][8][7]     ← min(7,6)+2=8, min(6,8)+1=7

Answer: 7 (Path: 1→3→1→1→1 or 1→1→5→1→1? Let’s trace!)

Best path: 1 → 1 → 5 → 1 → 1? No wait… Best path: 1 → 3 → 1 → 1 → 1 = 7 ✓

The Magic Formula

// For any cell (i, j):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Translation: Cost to reach me = My toll + Cheaper of (cost from above, cost from left).

Java Code

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int 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];
    }

    // Fill the rest
    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];
}

Visual Decision

graph TD
    A["At any cell"] --> B{"Where did I come from?"}
    B --> C["From Above<br/>cost = dp[i-1][j]"]
    B --> D["From Left<br/>cost = dp[i][j-1]"]
    C --> E["Pick MINIMUM"]
    D --> E
    E --> F["Add my toll<br/>+ grid[i][j]"]
    F --> G["That's my total cost!"]

The Pattern: Grid DP Recipe

Every Grid DP problem follows this recipe:

Step 1: Define What dp[i][j] Means

• Unique Paths: “Number of ways to reach cell (i,j)”
• Min Path Sum: “Minimum cost to reach cell (i,j)”

Step 2: Find the Base Cases

• First row: Can only come from the left
• First column: Can only come from above
• Starting cell: Usually given or simple

Step 3: Write the Transition

Figure out how current cell depends on previous cells:

• Usually: dp[i][j] = f(dp[i-1][j], dp[i][j-1])

Step 4: Fill Order

• Go row by row, left to right
• Or column by column, top to bottom

Step 5: Return Answer

• Usually dp[m-1][n-1] (bottom-right corner)

Real-Life Examples

Video Games

• Shortest path in a tile-based game
• Counting routes in maze games

Maps & Navigation

• Finding routes in city grids (like Manhattan!)
• Robot path planning in warehouses

Image Processing

• Finding seams for resizing images
• Pattern matching in 2D data

Quick Comparison

Pro Tips

1. Space Optimization: You only need the previous row! Can reduce from O(m×n) to O(n) space.

2. Edge Cases:

   • 1×1 grid? Answer is right there!
   • Empty grid? Handle it!

3. Obstacles: Some problems have blocked cells. Just mark them as impossible (0 for paths, infinity for costs).

4. Direction Variations: Some problems allow all 4 directions - that’s a different pattern (BFS/DFS)!

You Did It!

Grid DP is like playing chess on a checkerboard where you can only move right or down. By remembering what happened at each square, you avoid repeating work and find answers quickly.

Remember:

• Unique Paths = COUNT by ADDING from above and left
• Min Path Sum = OPTIMIZE by CHOOSING the better path

Now you’re ready to tackle any grid that comes your way! 🎯