Unique Paths in Grid DP in DSA Rust

Mental Model

Count how many ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down.

Analogy: Imagine walking through a city grid where you can only go east or south. You want to know how many different routes you can take to reach your friend's house at the bottom-right corner.

Start (S) at top-left, End (E) at bottom-right:
S -> -> ->
↓   ↓   ↓
-> -> -> E

Dry Run Walkthrough

Input: grid size: 3 rows x 3 columns

Goal: Find the number of unique paths from top-left to bottom-right moving only right or down

Step 1: Initialize a 3x3 grid with 1s in the first row and first column

[1] [1] [1]
[1] [ ] [ ]
[1] [ ] [ ]

Why: Only one way to reach cells in first row (all right moves) and first column (all down moves)

Step 2: Calculate paths for cell (1,1) by adding paths from top (0,1) and left (1,0)

[1] [1] [1]
[1] [2] [ ]
[1] [ ] [ ]

Why: Paths to (1,1) = paths from above + paths from left = 1 + 1 = 2

Step 3: Calculate paths for cell (1,2) by adding paths from top (0,2) and left (1,1)

[1] [1] [1]
[1] [2] [3]
[1] [ ] [ ]

Why: Paths to (1,2) = 1 + 2 = 3

Step 4: Calculate paths for cell (2,1) by adding paths from top (1,1) and left (2,0)

[1] [1] [1]
[1] [2] [3]
[1] [3] [ ]

Why: Paths to (2,1) = 2 + 1 = 3

Step 5: Calculate paths for cell (2,2) by adding paths from top (1,2) and left (2,1)

[1] [1] [1]
[1] [2] [3]
[1] [3] [6]

Why: Paths to (2,2) = 3 + 3 = 6

Result:

Final grid with path counts:
[1] [1] [1]
[1] [2] [3]
[1] [3] [6]
Answer: 6 unique paths

Annotated Code

DSA Rust

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() {
    let m = 3;
    let n = 3;
    let result = unique_paths(m, n);
    println!("{} unique paths", result);
}

let mut dp = vec![vec![1; n]; m];

Initialize grid with 1s in first row and column representing base paths

for i in 1..m {

Start filling dp from second row

for j in 1..n {

Start filling dp from second column

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

Sum paths from top and left cells to get current cell paths

dp[m - 1][n - 1]

Return total paths to bottom-right corner

Output

6 unique paths

Complexity Analysis

Time: O(m*n) because we fill each cell in the grid once

Space: O(m*n) because we store path counts for each cell in a 2D array

vs Alternative: Compared to recursive approach without memoization which is exponential, this DP approach is efficient and avoids repeated calculations

Edge Cases

Grid with 1 row or 1 column

Only one path exists since movement is only in one direction

DSA Rust

let mut dp = vec![vec![1; n]; m];

Grid size 0 (m=0 or n=0)

Function panics due to out-of-bounds access; logically 0 paths

DSA Rust

No explicit guard; input should be positive integers

When to Use This Pattern

When asked to count ways to reach a point in a grid with restricted moves, use DP to build solutions from smaller subproblems.

Common Mistakes

Mistake: Starting loops from 0 instead of 1 causing index errors or overwriting base cases
Fix: Start loops from 1 to preserve first row and column base paths

Mistake: Not initializing first row and column with 1s
Fix: Initialize dp grid with 1s to represent single path along edges

Summary

Calculates number of unique paths in a grid moving only right or down.

Use when counting routes in grid-like problems with movement constraints.

Each cell's paths equal sum of paths from above and left cells.

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