Unique Paths in Grid DP in DSA Rust - 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 and avoid repeating work. This helps solve the problem efficiently even for big grids. The result is 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 dynamic programming can turn a slow, repetitive task into a fast one by saving answers to smaller problems. It helps in many real-world cases like robot movement, game design, and route planning where you need to count or find paths quickly.

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 those with obstacles or variable moves, and then move on to graph algorithms and shortest path problems.

Mental Model

Core Idea

Count the ways to reach each cell by adding the ways to reach the cell above and the cell to the 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 street above or the street to the left. The total ways to get there is the sum of ways to get to those two streets.

Grid example (3x3):
┌───┬───┬───┐
│ 1 │ 1 │ 1 │
├───┼───┼───┤
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 1 │ 3 │ 6 │
└───┴───┴───┘
Each cell shows number of unique paths 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. 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 limits the problem and makes counting paths manageable.

2

Foundation

Brute Force Counting Paths Recursively

Concept: Count paths by trying all possible moves recursively.

From each cell, try moving right and down recursively until you reach the bottom-right. Count 1 for each successful path. This method repeats many calculations.

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 table to store the number of ways to reach each cell.

Create a 2D array dp with the same size as the grid. Initialize dp[0][0] = 1 because there's one way to start. For the first row and first column, set dp values to 1 because you can only move straight right or down.

Result

A table ready to fill with path counts.

Setting up the table prepares for efficient calculation by storing intermediate results.

4

Intermediate

Filling DP Table Using Previous Results

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

Concept: Calculate dp[i][j] by adding dp[i-1][j] and dp[i][j-1].

For each cell not in the first row or column, the number of ways to get there equals the sum of ways to get to the cell above plus the cell to the left. This uses the idea that you can only come from those two directions.

Result

The dp table fills with correct path counts for all cells.

Knowing that each cell depends only on two neighbors simplifies the problem and avoids redundant calculations.

5

Intermediate

Implementing DP Solution in Rust

Concept: Write Rust code to build and fill the dp table and return the final count.

Use a vector of vectors to represent dp. Initialize first row and column to 1. Loop through the grid, update dp[i][j] = dp[i-1][j] + dp[i][j-1]. Return dp[m-1][n-1].

Result

Rust code that efficiently computes unique paths.

Implementing in code solidifies understanding and shows practical use of DP.

6

Advanced

Optimizing Space Usage in DP

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

Concept: Use a single 1D array to store current row results, updating in place.

Since dp[i][j] depends only on dp[i-1][j] (previous row) and dp[i][j-1] (current row left), we can keep one array representing the current row. Update it as we move through columns.

Result

Memory usage reduces from O(m*n) to O(n).

Understanding dependencies allows memory optimization without losing correctness.

7

Expert

Handling Obstacles and Variations

🤔Before reading on: do you think the same DP approach works if some cells are blocked? Commit to your answer.

Concept: Modify DP to skip blocked cells by setting their path count to zero.

If a cell is blocked, set dp value to 0. For other cells, sum neighbors only if they are not blocked. This changes the counting but keeps the DP structure.

Result

DP adapts to grids with obstacles, counting only valid paths.

Knowing how to adjust DP for constraints extends its power to real-world problems.

Under the Hood

The DP table stores the number of ways to reach each cell. Each cell's value is computed once by adding the values from the cell above and the cell to the left. This avoids recalculating paths multiple times, turning an exponential problem into a polynomial one. Memory stores intermediate results, and iteration fills the table systematically.

Why designed this way?

This approach was designed to solve the inefficiency of brute force recursion, which repeats calculations. By storing results, it trades extra memory for speed. The problem's structure naturally fits this because each cell depends only on two neighbors, making the solution simple and elegant.

┌─────────────┐
│ Start (0,0) │
└─────┬───────┘
      │
┌─────▼───────┐
│ dp Table    │
│ ┌─────────┐ │
│ │ 1 1 1   │ │
│ │ 1 2 3   │ │
│ │ 1 3 6   │ │
│ └─────────┘ │
└─────┬───────┘
      │
┌─────▼───────┐
│ Result = 6  │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think the number of unique paths grows linearly with grid size? Commit to yes or no.

Common Belief: The number of unique paths increases linearly as the grid gets bigger.

Reality: The number of unique paths grows combinatorially, much faster than linear growth.

Why it matters: Underestimating growth leads to inefficient algorithms that can't handle large grids.

Quick: Do you think you can move diagonally in the unique paths problem? Commit to yes or no.

Common Belief: You can move diagonally as well as right and down.

Reality: Only right and down moves are allowed; diagonal moves are not considered.

Why it matters: Allowing diagonal moves changes the problem and the counting method completely.

Quick: Do you think the DP table must be fully stored in memory for the solution? Commit to yes or no.

Common Belief: You must keep the entire 2D DP table in memory to solve the problem.

Reality: You can optimize space by using a single 1D array since each row depends only on the previous row.

Why it matters: Knowing this prevents unnecessary memory use, important for large grids or limited memory.

Quick: Do you think the DP approach fails if some cells are blocked? Commit to yes or no.

Common Belief: The DP method cannot handle grids with obstacles or blocked cells.

Reality: DP can be adapted by setting blocked cells' path counts to zero and skipping them in calculations.

Why it matters: Believing this limits the use of DP in practical scenarios like robot navigation with obstacles.

Expert Zone

1

The order of filling the DP table matters; row-wise or column-wise traversal must respect dependencies.

2

When optimizing space, careful update order in the 1D array is crucial to avoid overwriting needed values.

3

The problem's combinatorial nature links to binomial coefficients, allowing direct formula solutions for unique paths without obstacles.

When NOT to use

This DP approach is not suitable when moves are allowed in more directions (like diagonal or backward), or when path costs vary and shortest path is needed. In such cases, graph algorithms like Dijkstra or A* are better.

Production Patterns

In real systems, this DP pattern is used in robotics for path planning on grids, in games for movement options, and in logistics for counting route possibilities. It often integrates with obstacle detection and dynamic updates.

Connections

Pascal's Triangle

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

Recognizing this connection allows using combinatorial formulas to compute unique paths directly without DP.

Graph Theory

The grid can be seen as a directed graph where edges represent allowed moves; counting paths is counting routes in the graph.

Understanding the grid as a graph opens doors to more complex pathfinding algorithms and optimizations.

Combinatorics in Probability

Counting unique paths is a combinatorial problem similar to calculating probabilities of sequences of events.

This link helps in understanding how counting paths relates to real-world problems like predicting outcomes and decision trees.

Common Pitfalls

#1 Confusing the allowed moves and trying to move diagonally.

Wrong approach:

if i > 0 && j > 0 {
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]; // wrong: includes diagonal
}

Correct approach:

if i > 0 && j > 0 {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // correct: only up and left
}

Root cause:

Misunderstanding problem constraints about allowed moves.

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

Wrong approach:

for i in 0..m {
for j in 0..n {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // fails at edges
}
}

Correct approach:

for i in 0..m {
dp[i][0] = 1;
}
for j in 0..n {
dp[0][j] = 1;
}
for i in 1..m {
for j in 1..n {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}

Root cause:

Ignoring base cases leads to incorrect sums and runtime errors.

#3 Using recursion without memoization causes exponential time.

Wrong approach:

fn count_paths(i: usize, j: usize) -> usize {
if i == 0 && j == 0 { return 1; }
let up = if i > 0 { count_paths(i-1, j) } else { 0 };
let left = if j > 0 { count_paths(i, j-1) } else { 0 };
up + left
}

Correct approach:

Use a dp table or memoization to store results and avoid repeated calls.

Root cause:

Not storing intermediate results causes repeated calculations and slow performance.

Key Takeaways

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

Dynamic programming saves time by storing intermediate results, avoiding repeated work.

Initializing the first row and column is crucial as base cases for the DP table.

Space can be optimized from 2D to 1D array by understanding dependencies between rows.

The approach adapts to obstacles by marking blocked cells with zero paths, showing DP's flexibility.

Practice

1. What does the problem "Unique Paths in Grid DP" ask you to find?
Unique Paths means:

easy

A. The number of ways to move from the top-left to bottom-right corner of a grid using only right and down moves

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

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

D. The number of obstacles in the grid

Solution

1. Step 1: Understand the problem goal

   The problem asks for counting all possible paths from the top-left corner to the bottom-right corner of a grid.

2. Step 2: Identify allowed moves

   Only moves to the right or down are allowed, so paths are sequences of these moves.

3. Final Answer:

   The number of ways to move from the top-left to bottom-right corner of a grid using only right and down moves -> Option A

4. Quick Check:

   Unique Paths = Count of right/down move sequences [OK]

Hint: Count paths with only right and down moves [OK]

Common Mistakes:

• Thinking about shortest path length instead of count
• Including diagonal or left moves
• Confusing with maximum sum path

2. Which of the following Rust code snippets correctly initializes a 2D vector dp of size m x n with all values set to 1?

easy

A. let dp = vec![vec![0; m]; n];

B. let dp = vec![vec![1; m]; n];

C. let dp = vec![vec![0; n]; m];

D. let dp = vec![vec![1; n]; m];

Solution

1. Step 1: Understand vector dimensions

   We want a vector with m rows and n columns, so outer vector length is m, inner vector length is n.

2. Step 2: Check initialization values

   All values should be 1, so inner vector is vec![1; n], repeated m times.

3. Final Answer:

   let dp = vec![vec![1; n]; m]; -> Option D

4. Quick Check:

   Outer length = m, inner length = n, all 1s [OK]

Hint: Outer vector size = rows (m), inner vector size = cols (n) [OK]

Common Mistakes:

• Swapping m and n in vector sizes
• Initializing with zeros instead of ones
• Using incorrect vector syntax

3. What is the output of the following Rust code for m = 3 and n = 3?

fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![1; n]; m];
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    dp[m-1][n-1]
}

fn main() {
    println!("{}", unique_paths(3, 3));
}

medium

A. 9

B. 6

C. 3

D. 1

Solution

1. Step 1: Initialize dp with 1s

   dp is a 3x3 grid with all 1s initially.

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

   Calculate dp values row by row: - dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2 - dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3 - dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3 - dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Use dp formula and fill row-wise [OK]

Common Mistakes:

• Not initializing first row and column with 1
• Adding dp[i][j-1] and dp[i-1][j] incorrectly
• Returning wrong dp cell

4. Identify the bug in this Rust function for unique paths and select the fix:

fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![0; n]; m];
    for i in 0..m {
        for j in 0..n {
            if i == 0 || j == 0 {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    dp[m][n]
}

medium

A. Change return to dp[m-1][n-1]

B. Initialize dp with ones instead of zeros

C. Change loops to start from 1 instead of 0

D. Remove the if condition inside loops

Solution

1. Step 1: Check dp indexing at return

   dp indices go from 0 to m-1 and 0 to n-1, so dp[m][n] is out of bounds and causes error.

2. Step 2: Fix return statement

   Return dp[m-1][n-1] to get bottom-right cell value.

3. Final Answer:

   Change return to dp[m-1][n-1] -> Option A

4. Quick Check:

   Return dp[m-1][n-1] to avoid index error [OK]

Hint: Return dp[m-1][n-1], not dp[m][n] [OK]

Common Mistakes:

• Returning dp[m][n] causing runtime panic
• Not initializing first row and column
• Starting loops incorrectly

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?
Choose the correct approach:

hard

A. Use recursion without memoization to skip obstacles

B. Ignore obstacles and use normal unique paths formula; obstacles don't affect path count

C. Initialize dp with zeros; set dp[0][0] = 1 if no obstacle; for each cell, if obstacle, dp[i][j] = 0 else dp[i][j] = dp[i-1][j] + dp[i][j-1]

D. Initialize dp with ones everywhere; subtract paths passing through obstacles at the end

Solution

1. Step 1: Initialize dp considering obstacles

   Set dp cells to 0 if obstacle present; dp[0][0] = 1 only if start is free.

2. Step 2: Update dp values skipping obstacles

   For each cell, if obstacle, dp[i][j] = 0; else dp[i][j] = dp[i-1][j] + dp[i][j-1]. This counts only valid paths.

3. Final Answer:

   Initialize dp with zeros; set dp[0][0] = 1 if no obstacle; for each cell, if obstacle, dp[i][j] = 0 else dp[i][j] = dp[i-1][j] + dp[i][j-1] -> Option C

4. Quick Check:

   Obstacles block paths by setting dp cells to zero [OK]

Hint: Set dp[i][j] = 0 for obstacles, sum neighbors otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Subtracting paths after counting all
• Using recursion without memoization causing inefficiency