Unique Paths in Grid DP in DSA Typescript - Deep Dive

Overview - Unique Paths in Grid DP

What is it?

Unique Paths in Grid DP is a way to count how many different ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down. It uses a method called dynamic programming to remember past results so it doesn't repeat work. This helps solve the problem efficiently even for big grids. The goal is to find the total number of unique routes you can take.

Why it matters

Without this method, counting all possible paths would take too long because the number grows very fast as the grid gets bigger. This problem shows how breaking a big problem into smaller parts and remembering answers saves time. It helps in many real-world tasks like robot navigation, game moves, or planning routes. Without it, computers would waste time recalculating the same paths again and again.

Where it fits

Before learning this, you should understand basic loops, arrays, and simple recursion. After this, you can learn more complex dynamic programming problems like grid problems with obstacles or minimum path sums. This topic is a stepping stone to mastering efficient problem solving with dynamic programming.

Mental Model

Core Idea

Count the ways to reach each cell by adding ways from the cell above and the cell to the left, building up from the start.

Think of it like...

Imagine walking through a city grid where you can only move east or south. To get to any intersection, you can come from the street above or the street to the west. The total ways to get there is the sum of ways to get to those two streets.

Start (0,0)
  ↓       ->
(0,1) -> (0,2) -> ... -> (0,n-1)
  ↓       ↓             ↓
(1,0) -> (1,1) -> ... -> (1,n-1)
  ↓       ↓             ↓
...     ...           ...
  ↓       ↓             ↓
(m-1,0) -> ... -> ... -> End (m-1,n-1)

Each cell = ways from above + ways from left

Build-Up - 7 Steps

1

Foundation

Understanding the grid and moves

Concept: Introduce the grid layout and allowed moves (right and down).

Imagine a grid with rows and columns. You start at the top-left corner (0,0). You can only move right (increase column) or down (increase row). The goal is to reach the bottom-right corner (m-1, n-1).

Result

You know the problem setup and allowed moves.

Understanding allowed moves sets the stage for counting paths without confusion.

2

Foundation

Brute force path counting

Concept: Count paths by exploring all possible moves recursively.

From each cell, try moving right or down until you reach the end. Count each successful path. This method tries every route but repeats work many times.

Result

You get the total number of paths but with slow performance for big grids.

Seeing the brute force method shows why we need a better way to avoid repeated work.

3

Intermediate

Dynamic programming table setup

Concept: Use a 2D table to store the number of ways to reach each cell.

Create a 2D array dp with the same size as the grid. dp[i][j] will hold the number of unique paths to cell (i,j). Initialize dp[0][0] = 1 because there's only one way to start.

Result

You have a structure to store answers for subproblems.

Storing results prevents recalculating paths for the same cell multiple times.

4

Intermediate

Filling the DP table with sums

🤔Before reading on: do you think the number of ways to reach a cell depends on one or two neighboring cells? Commit to your answer.

Concept: Each cell's ways equal the sum of ways from the cell above and the cell to the left.

For each cell (i,j), dp[i][j] = dp[i-1][j] + dp[i][j-1]. If i or j is 0, only one direction is possible, so dp[i][j] = 1. Fill the table row by row or column by column.

Result

The dp table contains the count of unique paths to every cell.

Knowing that each cell depends only on two neighbors simplifies the problem and enables efficient computation.

5

Intermediate

Implementing DP in TypeScript

🤔Before reading on: do you think a nested loop or recursion with memoization is simpler for this problem? Commit to your answer.

Concept: Translate the DP logic into TypeScript code using loops.

function uniquePaths(m: number, n: number): number { const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0)); for (let i = 0; i < m; i++) { dp[i][0] = 1; } for (let j = 0; j < n; j++) { dp[0][j] = 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]; } console.log(uniquePaths(3, 3));

Result

Output: 6

Implementing DP with loops is straightforward and efficient for this problem.

6

Advanced

Optimizing space usage

🤔Before reading on: do you think we need to store the entire 2D table or can we reduce memory? Commit to your answer.

Concept: Use a single array to store current row results, reducing space from O(m*n) to O(n).

Since dp[i][j] depends only on dp[i-1][j] (previous row) and dp[i][j-1] (current row left), we can use one array dp of length n. Initialize dp with 1s. For each row from 1 to m-1, update dp[j] += dp[j-1].

Result

Memory usage is reduced while keeping correct path counts.

Understanding dependencies allows memory optimization without losing correctness.

7

Expert

Mathematical combinatorics formula

🤔Before reading on: do you think counting paths can be done without DP using math? Commit to your answer.

Concept: The number of unique paths equals the number of ways to arrange moves: (m-1) downs and (n-1) rights in any order.

Total moves = (m-1) + (n-1) = m+n-2. The problem reduces to choosing positions for either downs or rights. The formula is C(m+n-2, m-1) or C(m+n-2, n-1), where C is the binomial coefficient. This can be computed efficiently using factorial or iterative multiplication.

Result

You can compute unique paths instantly without building a DP table.

Recognizing the problem as a combinatorial one reveals a direct formula, offering a faster solution for large grids.

Under the Hood

The DP solution builds a table where each cell stores the count of unique paths to reach it. It uses the fact that to get to a cell, you must come from either the cell above or the cell to the left. By summing these two counts, it avoids recalculating paths repeatedly. The process fills the table row by row or column by column, ensuring all dependencies are computed before use.

Why designed this way?

This approach was designed to solve the exponential time problem of brute force recursion. By storing intermediate results, it trades space for time, making the solution efficient. Alternatives like pure recursion are too slow, and the combinatorial formula, while fast, is less intuitive and harder to extend to variations like obstacles.

┌─────────────┐
│ Start (0,0) │
└─────┬───────┘
      │
      ▼
┌─────┴───────┐
│ dp Table    │
│ +---------+ │
│ | 1  1  1 | │
│ | 1  2  3 | │
│ | 1  3  6 | │
│ +---------+ │
└─────────────┘

Each cell = ways from above + ways from left

Myth Busters - 3 Common Misconceptions

Quick: Do you think the number of unique paths changes if you can move diagonally? Commit yes or no.

Common Belief: People often think the unique paths count stays the same regardless of allowed moves.

Reality: Allowing diagonal moves changes the problem and increases the number of unique paths significantly.

Why it matters: Using the wrong movement rules leads to incorrect path counts and wrong solutions.

Quick: Do you think the DP table stores the actual paths? Commit yes or no.

Common Belief: Some believe the DP table stores the full paths taken to reach each cell.

Reality: The DP table only stores the count of paths, not the paths themselves.

Why it matters: Confusing counts with actual paths can cause misunderstanding of what DP solves and how to reconstruct paths if needed.

Quick: Do you think the combinatorial formula always works even with obstacles? Commit yes or no.

Common Belief: Many think the combinatorial formula applies to all grid path problems.

Reality: The formula only works for empty grids without obstacles; obstacles require DP or other methods.

Why it matters: Applying the formula blindly leads to wrong answers in real-world scenarios with blocked cells.

Expert Zone

1

The DP approach can be adapted to count paths with constraints by modifying the recurrence or initial conditions.

2

Space optimization from 2D to 1D DP arrays relies on the problem's dependency pattern and is not always possible.

3

Floating-point precision can affect combinatorial calculations for very large grids, requiring careful implementation.

When NOT to use

Avoid DP when the grid is extremely large and only the count is needed; use the combinatorial formula instead. If obstacles or other constraints exist, DP or backtracking with memoization is necessary.

Production Patterns

In production, this pattern is used in robotics for path planning, in games for move counting, and in logistics for route optimization. Often combined with obstacle handling and cost minimization for practical use.

Connections

Pascal's Triangle

The DP table values correspond to entries in Pascal's Triangle representing binomial coefficients.

Understanding Pascal's Triangle helps grasp the combinatorial nature of unique paths and the DP sums.

Memoization in Recursion

DP here is a bottom-up version of memoized recursion that caches results to avoid repeated work.

Knowing memoization clarifies why DP improves performance by storing intermediate results.

Probability Theory

Counting unique paths relates to calculating probabilities of sequences of moves in random walks.

This connection shows how combinatorics and DP underpin models in statistics and physics.

Common Pitfalls

#1 Not initializing the first row and first column to 1.

Wrong approach:

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

Correct approach:

for (let i = 0; i < m; i++) dp[i][0] = 1;
for (let j = 0; j < n; j++) dp[0][j] = 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];
}
}

Root cause:

Failing to handle edge cases where only one path exists along the first row or column.

#2 Using recursion without memoization causing exponential time.

Wrong approach:

function countPaths(i, j) {
if (i === 0 && j === 0) return 1;
if (i < 0 || j < 0) return 0;
return countPaths(i-1, j) + countPaths(i, j-1);
}
console.log(countPaths(m-1, n-1));

Correct approach:

Use a dp array to store results or convert to bottom-up DP to avoid repeated calculations.

Root cause:

Not storing intermediate results leads to repeated calculations and slow performance.

#3 Applying combinatorial formula when obstacles exist.

Wrong approach:

function uniquePaths(m, n) {
return factorial(m+n-2) / (factorial(m-1) * factorial(n-1));
}
// Used on grid with obstacles

Correct approach:

Use DP that checks for obstacles and skips blocked cells when counting paths.

Root cause:

Misunderstanding problem constraints and blindly applying formulas.

Key Takeaways

Unique Paths in Grid DP counts ways to reach each cell by summing paths from above and left cells.

Dynamic programming avoids repeated work by storing intermediate results in a table.

Initializing the first row and column correctly is crucial for accurate path counts.

The problem can also be solved using a combinatorial formula for empty grids, offering a fast alternative.

Understanding dependencies and problem constraints guides whether to use DP, combinatorics, or other methods.