Why Unique Paths in Grid DP in DSA Typescript?

The Big Idea

What if you could count thousands of paths in seconds without writing them all down?

The Scenario

Imagine you are in a big city grid with streets laid out in rows and columns. You want to walk from your home at the top-left corner to your friend's house at the bottom-right corner. You can only walk right or down. Counting all possible ways by hand is like listing every single path on a huge map.

The Problem

Trying to count all paths manually is slow and confusing. As the grid grows, the number of paths grows very fast, making it impossible to keep track without mistakes. You might forget some paths or count some twice. It's like trying to count every grain of sand on a beach by hand.

The Solution

Dynamic Programming (DP) breaks this big problem into smaller, easy steps. It remembers how many ways to reach each spot in the grid, building up the answer step-by-step. This way, you don't have to list all paths, just add up smaller results. It's like using a map with notes on how many ways to get to each intersection.

Before vs After

✗ Before

function countPaths(m: number, n: number): number {
  // Try all paths recursively (slow)
  if (m === 1 || n === 1) return 1;
  return countPaths(m - 1, n) + countPaths(m, n - 1);
}

✓ After

function countPaths(m: number, n: number): number {
  const dp: number[][] = Array(m).fill(0).map(() => Array(n).fill(1));
  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];
}

What It Enables

It lets you quickly find how many ways to reach any point in a grid without listing every path, saving time and avoiding mistakes.

Real Life Example

Delivery drivers use similar calculations to find how many routes they can take through city blocks when they can only move right or down, helping them plan efficient deliveries.

Key Takeaways

Manual counting of paths is slow and error-prone.

Dynamic Programming breaks the problem into smaller parts and remembers results.

This method quickly calculates total unique paths in a grid.