Grid DP

🗺️ Grid DP: Finding Your Way Through a Maze

The Story of the Maze Runner

Imagine you’re a tiny robot 🤖 standing at the top-left corner of a grid. Your mission? Reach the treasure chest at the bottom-right corner!

But here’s the twist: you can only move RIGHT or DOWN. No going back, no going up. Just like a one-way street!

This is Grid Dynamic Programming — and once you understand it, you’ll feel like a path-finding wizard! 🧙‍♂️

🎯 What is DP on Grids?

Think of a grid like a chocolate bar 🍫 with squares. Each square is a “cell” you can visit.

The Big Idea:

To know the best way to reach ANY cell, just look at the cells that could have led to it (the one above and the one to the left).

graph TD
    A["Start 🏁"] --> B["Move Right →"]
    A --> C["Move Down ↓"]
    B --> D["Keep Going..."]
    C --> D
    D --> E["Reach Goal 🎯"]

Why is this powerful?

• Instead of trying every possible path (which takes forever! ⏰)
• We build our answer step by step
• Each cell remembers its answer so we don’t repeat work

🛤️ Unique Paths: How Many Roads Lead to Treasure?

The Problem

You have a grid with m rows and n columns. Starting from top-left, how many different ways can you reach bottom-right?

Real-Life Analogy 🏙️

Imagine walking in a city with streets forming a grid. You can only walk East or South. How many different routes exist to reach the park?

START ──→──→──→
  ↓         ↓
  ↓    →    ↓
  ↓         ↓
  →────→── PARK

The Magic Formula ✨

For any cell (i, j):

paths[i][j] = paths[i-1][j] + paths[i][j-1]
              ↑              ↑
        from above    from left

Translation: The ways to reach a cell = ways from above + ways from left!

Step-by-Step Example

Let’s find paths in a 3×3 grid:

┌───┬───┬───┐
│ 1 │ 1 │ 1 │  ← Only one way along top edge
├───┼───┼───┤
│ 1 │ 2 │ 3 │  ← 2 = 1+1, 3 = 1+2
├───┼───┼───┤
│ 1 │ 3 │ 6 │  ← Answer: 6 paths! 🎉
└───┴───┴───┘

The Code 💻

function uniquePaths(m, n) {
  // Create grid filled with 1s
  const dp = Array(m).fill(null)
    .map(() => Array(n).fill(1));

  // Fill in the magic numbers
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  }

  return dp[m-1][n-1];
}

// Example: 3x3 grid
console.log(uniquePaths(3, 3)); // Output: 6

Why First Row & Column are All 1s? 🤔

• First row: Only one way — keep going RIGHT →→→
• First column: Only one way — keep going DOWN ↓↓↓

No choices means exactly 1 path!

💰 Minimum Path Sum: Cheapest Route to the Treasure

The Problem

Now each cell has a cost (think of it as coins you must pay). Find the path with the lowest total cost.

Real-Life Analogy 🚗

You’re driving through toll booths. Each road segment has a toll fee. Find the cheapest route from home to work!

┌─────┬─────┬─────┐
│ $1  │ $3  │ $1  │
├─────┼─────┼─────┤
│ $1  │ $5  │ $1  │
├─────┼─────┼─────┤
│ $4  │ $2  │ $1  │
└─────┴─────┴─────┘

The Magic Formula ✨

For any cell (i, j):

minCost[i][j] = grid[i][j] + min(
  minCost[i-1][j],    // cost from above
  minCost[i][j-1]     // cost from left
)

Translation: Minimum cost = cell’s cost + cheaper of (coming from above OR left)

Step-by-Step Example

Using the grid above:

Original:          Minimum Costs:
┌───┬───┬───┐      ┌───┬───┬───┐
│ 1 │ 3 │ 1 │      │ 1 │ 4 │ 5 │
├───┼───┼───┤  →   ├───┼───┼───┤
│ 1 │ 5 │ 1 │      │ 2 │ 7 │ 6 │
├───┼───┼───┤      ├───┼───┼───┤
│ 4 │ 2 │ 1 │      │ 6 │ 8 │ 7 │ ← Answer!
└───┴───┴───┘      └───┴───┴───┘

Cheapest path: 1→1→4→2→1 = $7 🎉

The Code 💻

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;

  // Build first row (can only come from left)
  for (let j = 1; j < n; j++) {
    grid[0][j] += grid[0][j-1];
  }

  // Build first column (can only come from above)
  for (let i = 1; i < m; i++) {
    grid[i][0] += grid[i-1][0];
  }

  // Fill rest with minimum of top or left
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i][j] += Math.min(
        grid[i-1][j],
        grid[i][j-1]
      );
    }
  }

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

// Example
const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
];
console.log(minPathSum(grid)); // Output: 7

🔑 Key Insights to Remember

Pattern Recognition 🧩

The Grid DP Recipe 📝

1. Create a DP table (same size as grid)
2. Fill base cases (first row & column)
3. Fill remaining cells using the formula
4. Answer is in bottom-right corner

graph TD
    A["Create DP Table"] --> B["Fill First Row"]
    B --> C["Fill First Column"]
    C --> D["Fill Remaining Cells"]
    D --> E["Return Bottom-Right Value"]

🚀 Pro Tips

Tip 1: Space Optimization

You don’t always need a full 2D array! For many grid problems, you only need the previous row:

// Space-optimized Unique Paths
function uniquePathsOptimized(m, n) {
  const dp = Array(n).fill(1);

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j-1];
    }
  }

  return dp[n-1];
}

Tip 2: Identify Grid DP Problems

Ask yourself:

• Can I only move in limited directions?
• Does each cell depend on previous cells?
• Am I counting paths or finding optimal value?

If yes → Grid DP! ✅

🎬 Summary: Your Grid DP Journey

You started as a confused traveler. Now you’re a Grid DP Master! 🏆

What you learned:

1. Grid DP breaks big problems into tiny cell-by-cell decisions
2. Unique Paths counts ways by adding paths from above and left
3. Minimum Path Sum finds cheapest route by choosing the minimum

Remember the mantra:

“To solve any cell, just look at where I came from!”

Now go forth and conquer those grids! 🗺️✨