Why Minimum Path Sum in Grid in DSA Typescript?

The Big Idea

What if you could instantly find the cheapest way through a maze of streets without trying every path?

The Scenario

Imagine you are walking through a city grid from the top-left corner to the bottom-right corner. Each block has a cost to cross, like traffic or tolls. You want to find the cheapest path to reach your destination.

The Problem

Trying every possible path manually is like checking every street and alley in the city. It takes too long and is easy to get lost or miss cheaper routes. This makes finding the best path slow and frustrating.

The Solution

Using the Minimum Path Sum method, we calculate the cheapest cost step-by-step, remembering the best cost to reach each block. This way, we avoid repeating work and quickly find the cheapest path.

Before vs After

✗ Before

function minPathSum(grid: number[][]): number {
  // Try all paths recursively - very slow
  function dfs(row: number, col: number): number {
    if (row === grid.length || col === grid[0].length) return Infinity;
    if (row === grid.length - 1 && col === grid[0].length - 1) return grid[row][col];
    return grid[row][col] + Math.min(dfs(row + 1, col), dfs(row, col + 1));
  }
  return dfs(0, 0);
}

✓ After

function minPathSum(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp: number[][] = Array(rows).fill(null).map(() => Array(cols).fill(0));
  dp[0][0] = grid[0][0];
  for (let i = 1; i < rows; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
  for (let j = 1; j < cols; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[rows - 1][cols - 1];
}

What It Enables

This method lets you quickly find the cheapest route through any grid, saving time and effort.

Real Life Example

Delivery drivers use this to find the least costly route through city blocks, saving fuel and time.

Key Takeaways

Manual checking of all paths is slow and inefficient.

Dynamic programming remembers best costs to avoid repeated work.

Minimum Path Sum finds the cheapest path through a grid efficiently.