Unique Paths in Grid DP in DSA C++ - 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 table to remember answers to smaller parts of the problem so we don't repeat work. This method helps solve problems where you want to find the number of possible routes in a grid with simple movement rules.

Why it matters

Without this method, counting all possible paths would take a very long time because you would try every route one by one. This would be slow and inefficient, especially for big grids. Using dynamic programming to find unique paths saves time and helps computers solve problems like robot movement, game maps, and route planning quickly and correctly.

Where it fits

Before learning this, you should understand basic loops, arrays, and simple recursion. After this, you can learn more complex grid problems like obstacles in grids, minimum path sums, or 2D dynamic programming problems that involve more conditions.

Mental Model

Core Idea

The number of ways to reach a cell is the sum of ways to reach the cell above it and the cell to its left.

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 intersection above or the one to the left. The total ways to get there is just adding those two possibilities.

Grid example (3x3):
┌───┬───┬───┐
│ 1 │ 1 │ 1 │
├───┼───┼───┤
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 1 │ 3 │ 6 │
└───┴───┴───┘
Each cell shows number of ways to reach it.

Build-Up - 7 Steps

1

Foundation

Understanding the Grid and Moves

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

We have a grid with rows and columns. Starting 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 Counting Paths Recursively

Concept: Count paths by trying all possible moves recursively.

Define a function that, at each cell, tries moving right and down recursively until it reaches the bottom-right. Sum all successful paths. This works but repeats many calculations.

Result

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

Seeing the brute force method reveals the problem of repeated work and motivates optimization.

3

Intermediate

Introducing Dynamic Programming Table

🤔Before reading on: do you think storing intermediate results can speed up counting paths? Commit to yes or no.

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

Create a 2D array dp where dp[i][j] means number of ways to reach cell (i,j). Initialize dp[0][0] = 1 since start is one way. Fill first row and first column with 1 because only one way to reach those cells (all right or all down). For other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1].

Result

The dp table fills with counts of paths for each cell, ending with dp[m-1][n-1] as the answer.

Knowing that each cell depends only on two neighbors simplifies the problem and avoids repeated work.

4

Intermediate

Implementing DP in C++ with Loops

🤔Before reading on: do you think nested loops or recursion is better for filling the dp table? Commit to your answer.

Concept: Use nested loops to fill the dp table iteratively for better performance and clarity.

Use two loops: outer for rows, inner for columns. Initialize dp[0][0] = 1. For first row and column, set dp[i][0] = 1 and dp[0][j] = 1. For others, dp[i][j] = dp[i-1][j] + dp[i][j-1]. Return dp[m-1][n-1].

Result

Efficient and clear code that calculates unique paths quickly.

Iterative filling of dp table is easier to understand and faster than recursion with memoization.

5

Intermediate

Optimizing Space Usage in DP

🤔Before reading on: can we reduce the 2D dp table to a 1D array? Commit to yes or no.

Concept: Since dp[i][j] depends only on dp[i-1][j] and dp[i][j-1], we can use a single array to save space.

Use a 1D array dp of size n (columns). Initialize all elements to 1 for the first row. For each next row, update dp[j] = dp[j] + dp[j-1]. This accumulates counts for each cell in the current row.

Result

Space usage reduces from O(m*n) to O(n) without changing the result.

Recognizing dependency patterns allows memory optimization, important for large grids.

6

Advanced

Handling Obstacles in the Grid

🤔Before reading on: do you think obstacles can be handled by simply skipping cells? Commit to yes or no.

Concept: Modify dp to account for blocked cells where no path can go through.

Given a grid with obstacles marked (e.g., 1 for obstacle, 0 for free), set dp[i][j] = 0 if cell is blocked. Otherwise, dp[i][j] = dp[i-1][j] + dp[i][j-1]. Initialize carefully to handle obstacles in first row and column.

Result

You get the count of unique paths avoiding obstacles.

Adapting the dp formula to obstacles shows the flexibility of the approach for real-world problems.

7

Expert

Mathematical Combinatorics Connection

🤔Before reading on: do you think the number of unique paths can be calculated without DP using math? Commit to yes or no.

Concept: The number of unique paths in an empty grid equals a combination formula from combinatorics.

To reach bottom-right in m x n grid, you must move (m-1) downs and (n-1) rights in any order. Total moves = (m-1)+(n-1). Number of unique paths = combinations of choosing (m-1) moves from total moves = C(m+n-2, m-1). This can be computed using factorial or iterative multiplication.

Result

You can calculate unique paths instantly without building dp tables.

Knowing the combinatorial formula provides a direct solution and deepens understanding of the problem's structure.

Under the Hood

Dynamic programming builds a table where each cell stores the number of ways to reach it. This works because the problem has overlapping subproblems and optimal substructure: the number of ways to a cell depends only on its immediate neighbors above and left. The dp table is filled row by row or column by column, reusing previously computed results to avoid repeated calculations.

Why designed this way?

This approach was designed to solve exponential time recursive problems efficiently by storing intermediate results. Alternatives like pure recursion are too slow for large grids. The dp method balances time and space complexity, making it practical for real applications like robotics and pathfinding.

┌───────────────┐
│ Start (0,0)   │
│ dp[0][0] = 1 │
└──────┬────────┘
       │
┌──────▼───────┐
│ dp[i][j] =   │
│ dp[i-1][j] + │
│ dp[i][j-1]   │
└──────┬───────┘
       │
┌──────▼─────────────┐
│ Fill dp table row by │
│ row or column by     │
│ reusing previous    │
│ results             │
└─────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the number of unique paths depend on the order of moves or just the count? Commit to your answer.

Common Belief: People often think the order of moves matters for counting unique paths.

Reality: The count depends only on how many moves right and down you make, not the order of those moves.

Why it matters: Misunderstanding this leads to overcomplicating the problem and incorrect counting.

Quick: Can you use the same dp formula if diagonal moves are allowed? Commit to yes or no.

Common Belief: Many believe the same dp formula applies even if diagonal moves are allowed.

Reality: If diagonal moves are allowed, the dp formula changes because each cell depends on three neighbors, not two.

Why it matters: Using the wrong formula causes wrong path counts and bugs in applications.

Quick: Is it always necessary to use a 2D dp table for unique paths? Commit to yes or no.

Common Belief: People think a 2D dp table is always needed to solve unique paths.

Reality: A 1D dp array can be used to save space because each row depends only on the previous row.

Why it matters: Not knowing this leads to inefficient memory use in large-scale problems.

Quick: Does the presence of obstacles always make the problem unsolvable? Commit to yes or no.

Common Belief: Some think that if there is any obstacle, no path exists.

Reality: Obstacles block some paths but often other paths still exist; dp can count paths avoiding obstacles.

Why it matters: Assuming no paths exist can cause premature failure or wrong results in pathfinding.

Expert Zone

1

The order of filling the dp table (row-wise or column-wise) can affect cache performance and runtime in large grids.

2

When using 1D dp arrays, careful initialization is needed to avoid mixing results from previous rows.

3

In combinatorial formula calculations, using iterative multiplication avoids overflow and improves numerical stability compared to factorials.

When NOT to use

This approach is not suitable when moves are not restricted to right and down or when the grid has complex constraints like variable costs or teleportation. In such cases, graph algorithms like BFS, DFS, or Dijkstra's algorithm are better alternatives.

Production Patterns

In real-world systems, unique paths DP is used in robotics for path planning, in games for map navigation, and in logistics for route optimization. Often combined with obstacle handling and cost calculations, it forms the basis for more complex grid-based algorithms.

Connections

Pascal's Triangle

The dp table for unique paths mirrors Pascal's Triangle values.

Understanding Pascal's Triangle helps grasp why dp[i][j] = dp[i-1][j] + dp[i][j-1] works as a sum of combinations.

Combinatorics

Unique paths count equals a combination formula from combinatorics.

Knowing combinatorics allows direct calculation of paths without building dp tables.

Urban Planning

Grid path counting models city block navigation problems.

Real-world city layouts often resemble grids, so unique paths DP helps in traffic flow and route planning.

Common Pitfalls

#1 Incorrectly initializing the first row and column of the dp table.

Wrong approach:

for (int i = 0; i < m; i++) dp[i][0] = 0;
for (int j = 0; j < n; j++) dp[0][j] = 0;

Correct approach:

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

Root cause:

Misunderstanding that there is exactly one way to reach cells in the first row or column by moving only right or down.

#2 Using dp[i][j] = dp[i-1][j-1] instead of dp[i][j] = dp[i-1][j] + dp[i][j-1].

Wrong approach:

dp[i][j] = dp[i-1][j-1];

Correct approach:

dp[i][j] = dp[i-1][j] + dp[i][j-1];

Root cause:

Confusing allowed moves and dependencies; diagonal moves are not allowed in this problem.

#3 Not handling obstacles by setting dp[i][j] = 0 for blocked cells.

Wrong approach:

if (obstacleGrid[i][j] == 1) dp[i][j] = dp[i-1][j] + dp[i][j-1];

Correct approach:

if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];

Root cause:

Failing to block paths through obstacles causes incorrect path counts.

Key Takeaways

Unique Paths in Grid DP counts ways to reach the bottom-right cell by summing paths from above and left cells.

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

Space optimization is possible by using a 1D array instead of a 2D table.

Obstacles can be handled by setting path counts to zero for blocked cells.

The problem has a direct combinatorial formula that can compute the answer instantly without DP.

Practice

1. What does the problem "Unique Paths in Grid DP" ask you to find?
Given a grid of size m x n, how many unique paths exist from the top-left corner to the bottom-right corner if you can only move right or down?

easy

A. The number of different ways to reach the bottom-right corner moving only right or down

B. The shortest path length from top-left to bottom-right

C. The maximum sum path from top-left to bottom-right

D. The number of obstacles in the grid

Solution

1. Step 1: Understand the problem statement

   The problem asks for counting all possible unique paths from the top-left to bottom-right corner of a grid, moving only right or down.

2. Step 2: Clarify what is being counted

   We count the number of ways to reach the destination, not the shortest path or sums.

3. Final Answer:

   The number of different ways to reach the bottom-right corner moving only right or down -> Option A

4. Quick Check:

   Unique paths count = number of ways [OK]

Hint: Count paths moving only right or down [OK]

Common Mistakes:

• Confusing path count with shortest path length
• Thinking about obstacles when none are given
• Mixing sum of values with path count

2. Which of the following is the correct way to initialize a 2D vector dp of size m x n with all values 0 in C++?

easy

A. std::vector dp(n, std::vector<int>(m));

B. std::vector<int> dp(m, n, 0);

C. std::vector dp(m, std::vector<int>(n, 0));

D. std::vector dp(m, std::vector<int>(n));

Solution

1. Step 1: Understand 2D vector initialization syntax

   In C++, a 2D vector is initialized by specifying rows and columns with default values.

2. Step 2: Check each option

   std::vector dp(m, std::vector<int>(n, 0)); correctly creates a vector with m rows and n columns, all initialized to 0.

3. Final Answer:

   std::vector dp(m, std::vector<int>(n, 0)); -> Option C

4. Quick Check:

   Correct 2D vector init syntax = std::vector dp(m, std::vector<int>(n, 0)); [OK]

Hint: Use vector of vectors with inner vector size and default value [OK]

Common Mistakes:

• Swapping m and n in initialization
• Using wrong vector constructor parameters
• Missing default value initialization

3. What is the output of the following C++ code snippet?

int m = 3, n = 3;
std::vector dp(m, std::vector<int>(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
  }
}
std::cout << dp[m-1][n-1] << std::endl;

medium

A. 3

B. 9

C. 10

D. 6

Solution

1. Step 1: Initialize first row and column

   First row and column are set to 1, representing only one path to each cell along edges.

2. Step 2: Fill dp table using dp[i][j] = dp[i-1][j] + dp[i][j-1]

   Calculate dp values for inner cells:
   dp[1][1] = 1+1=2
   dp[1][2] = 1+2=3
   dp[2][1] = 2+1=3
   dp[2][2] = 3+3=6

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Use DP formula dp[i][j] = dp[i-1][j] + dp[i][j-1] [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Using wrong indices in dp update
• Confusing addition with multiplication

4. Identify the error in the following code snippet for calculating unique paths in a grid:

int uniquePaths(int m, int n) {
  std::vector dp(m, std::vector<int>(n));
  for (int i = 0; i < m; i++) dp[i][0] = 1;
  for (int j = 0; j < n; j++) dp[0][j] = 1;
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] * dp[i][j-1];
    }
  }
  return dp[m-1][n-1];
}

medium

A. The multiplication operator should be addition in dp update

B. The dp vector is not initialized with zeros

C. The loops should start from 0 instead of 1

D. The return statement should be dp[0][0]

Solution

1. Step 1: Check dp update formula

   The code uses multiplication: dp[i][j] = dp[i-1][j] * dp[i][j-1], which is incorrect for counting paths.

2. Step 2: Correct formula for unique paths

   The correct formula adds the number of ways from top and left cells: dp[i][j] = dp[i-1][j] + dp[i][j-1].

3. Final Answer:

   The multiplication operator should be addition in dp update -> Option A

4. Quick Check:

   Use addition, not multiplication for path counts [OK]

Hint: Sum paths from top and left cells, don't multiply [OK]

Common Mistakes:

• Using multiplication instead of addition in dp formula
• Returning wrong dp cell
• Not initializing first row or column

5. Given a grid with obstacles represented by 1s and empty spaces by 0s, how would you modify the unique paths DP solution to count paths avoiding obstacles?
Consider the grid:

0 0 0
0 1 0
0 0 0

hard

A. Set dp[i][j] = 1 for all cells regardless of obstacles

B. Set dp[i][j] = 0 if grid[i][j] is 1, else dp[i][j] = dp[i-1][j] + dp[i][j-1]

C. Multiply dp[i-1][j] and dp[i][j-1] if obstacle is present

D. Ignore obstacles and use normal dp formula

Solution

1. Step 1: Handle obstacles in dp initialization

   If a cell has an obstacle (value 1), set dp[i][j] = 0 because no path can go through it.

2. Step 2: Update dp values considering obstacles

   For other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1], summing paths from top and left only if those cells are reachable.

3. Final Answer:

   Set dp[i][j] = 0 if grid[i][j] is 1, else dp[i][j] = dp[i-1][j] + dp[i][j-1] -> Option B

4. Quick Check:

   Obstacles block paths, set dp to 0 there [OK]

Hint: Zero dp for obstacles, sum paths otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Using multiplication instead of addition
• Setting dp to 1 for obstacle cells