Unique Paths in Grid DP in DSA Rust - Build from Scratch

Unique Paths in Grid DP

📖 Scenario: Imagine you are helping a robot find how many ways it can move from the top-left corner to the bottom-right corner of a grid. The robot can only move right or down.

🎯 Goal: Build a program that calculates the number of unique paths the robot can take in a grid of size m x n using dynamic programming.

📋 What You'll Learn

Create two variables m and n for grid dimensions

Create a 2D vector dp to store number of ways to reach each cell

Use nested for loops to fill dp with path counts

Print the number of unique paths from top-left to bottom-right

💡 Why This Matters

🌍 Real World

Robots and games often need to find ways to move through grids or maps efficiently.

💼 Career

Understanding dynamic programming and grid traversal is useful for software engineers working on pathfinding, AI, and optimization problems.

1

Set grid dimensions

Create two variables called m and n and set m = 3 and n = 3 to represent a 3 by 3 grid.

DSA Rust

# Your code here

Hint

Use let to create variables m and n with values 3.

2

Create DP table

Create a 2D vector called dp with m rows and n columns. Initialize all values to 1 using vec![vec![1; n]; m].

DSA Rust

fn main() {
    let m = 3;
    let n = 3;
    // Create dp vector with all 1s
    let mut dp = vec![vec![1; n]; m];
}

Hint

Use vec![vec![1; n]; m] to create a 2D vector filled with 1s.

3

Fill DP table with path counts

Use nested for loops with variables i from 1 to m-1 and j from 1 to n-1. Update dp[i][j] to be dp[i-1][j] + dp[i][j-1].

DSA Rust

fn main() {
    let m = 3;
    let n = 3;
    let mut dp = vec![vec![1; n]; m];
    // Fill dp with path counts
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
}

Hint

Use two for loops starting from 1 to update each cell by adding the value from above and left.

4

Print the number of unique paths

Print the value at dp[m - 1][n - 1] using println!("{}", dp[m - 1][n - 1]) to show the total unique paths.

DSA Rust

fn main() {
    let m = 3;
    let n = 3;
    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];
        }
    }
    // Print the total unique paths
    println!("{}", dp[m - 1][n - 1]);
}

Hint

The bottom-right cell dp[m - 1][n - 1] holds the total unique paths. Print it.

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