Grid DP

🗺️ Grid DP: Finding Your Way Through a Maze of Numbers

Imagine you’re a tiny explorer standing at the top-left corner of a checkerboard. Your mission? Get to the bottom-right corner. But here’s the twist—you can only move right or down. Welcome to Grid Dynamic Programming!

🎯 What is Grid DP?

Think of a grid like a big chocolate bar divided into squares. Grid DP is a clever way to solve problems where you need to move through this “chocolate bar” from one corner to another.

The Magic Rule: You can only go → right or ↓ down. No going back!

graph TD
    A["Start ↖"] --> B["Move Right →"]
    A --> C["Move Down ↓"]
    B --> D["Keep Going..."]
    C --> D
    D --> E["Reach End ↘"]

🚶 Unique Paths: How Many Ways Can You Get There?

The Story

Imagine you’re a little robot in a warehouse. You start at the top-left corner and need to reach the bottom-right corner to pick up a package. You can only move right or down.

Question: How many different paths can you take?

The Simple Idea

At each square, you can arrive from:

• The square above (came down)
• The square to the left (came right)

So the number of ways to reach any square = ways from above + ways from left!

Visual Example (3×3 Grid)

┌───┬───┬───┐
│ 1 │ 1 │ 1 │  ← Top row: only 1 way each
├───┼───┼───┤
│ 1 │ 2 │ 3 │  ← 2 = 1+1, 3 = 1+2
├───┼───┼───┤
│ 1 │ 3 │ 6 │  ← 6 paths to reach goal!
└───┴───┴───┘

Python Code

def uniquePaths(m, n):
    # Create a grid filled with 1s
    dp = [[1] * n for _ in range(m)]

    # Fill the grid
    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]

# Example: 3x3 grid
print(uniquePaths(3, 3))  # Output: 6

Why Does This Work?

First row and column are always 1 because there’s only one way to reach them (go straight right or straight down).

💰 Minimum Path Sum: The Cheapest Route

The Story

Now imagine each square has coins on it. Some squares have lots of coins (expensive!), some have few (cheap!). You want to find the path that picks up the fewest coins possible.

The Simple Idea

At each square, pick the cheaper way to arrive:

• Cost from above, OR
• Cost from the left

Add the current square’s cost to the cheaper option!

Visual Example

Grid with costs:        Minimum costs to reach:
┌───┬───┬───┐           ┌───┬───┬───┐
│ 1 │ 3 │ 1 │           │ 1 │ 4 │ 5 │
├───┼───┼───┤           ├───┼───┼───┤
│ 1 │ 5 │ 1 │    →      │ 2 │ 7 │ 6 │
├───┼───┼───┤           ├───┼───┼───┤
│ 4 │ 2 │ 1 │           │ 6 │ 8 │ 7 │
└───┴───┴───┘           └───┴───┴───┘

Minimum path cost = 7 ✨
Path: 1→3→1→1→1 or 1→1→5→1→1

Python Code

def minPathSum(grid):
    m, n = len(grid), len(grid[0])

    # Fill first row (can only come from left)
    for j in range(1, n):
        grid[0][j] += grid[0][j-1]

    # Fill first column (can only come from above)
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]

    # Fill rest of grid
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(
                grid[i-1][j],  # from above
                grid[i][j-1]   # from left
            )

    return grid[m-1][n-1]

# Example
grid = [[1,3,1], [1,5,1], [4,2,1]]
print(minPathSum(grid))  # Output: 7

🧠 The Grid DP Pattern (Your Secret Formula!)

Every Grid DP problem follows this recipe:

graph TD
    A["1. Create a DP table"] --> B["2. Handle base cases"]
    B --> C["3. Fill row by row"]
    C --> D["4. Use formula at each cell"]
    D --> E["5. Answer is at bottom-right"]

The Universal Formula

dp[i][j] = combine(dp[i-1][j], dp[i][j-1]) + current_value

🎮 Think of It Like a Video Game!

Unique Paths = “How many different ways can I complete this level?”

Minimum Path Sum = “What’s the lowest score I can finish with?”

Both games have the same rules:

• ➡️ Move right
• ⬇️ Move down
• 🚫 No going back

🌟 Key Takeaways

1. Grid DP = Table + Formula + Direction
2. Fill the table row by row, column by column
3. Each cell depends on its neighbors (top and left)
4. Base cases: first row and first column are special
5. Answer is always at the bottom-right corner

🎁 Memory Trick

“Right and Down, Fill the Town!”

Start at top-left, move right and down, Fill each square in your DP town!

Remember: Every square remembers the best way to reach it. That’s the magic of Dynamic Programming—building answers from smaller answers!

Now you’re ready to explore any grid and find your way through! 🗺️✨