Unique Paths in Grid DP in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP table with zeros.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A0usize

B1

CNone

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 for initialization

Using None which is invalid here

We initialize the DP table with zeros because initially, the number of paths to each cell is unknown and starts at zero.

2fill in blank

medium

Complete the code to set the number of paths for the first row cells.

DSA Rust

for j in 0..n {
    dp[0][j] = [1];
}

Drag options to blanks, or click blank then click option'

Aj

Bm

C1usize

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index j instead of 1

Using 0 which means no paths

The first row cells can only be reached by moving right, so each has exactly 1 path.

3fill in blank

hard

Fix the error in the code to correctly compute paths for other cells.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition

Using division which is invalid here

The number of paths to a cell is the sum of paths from the cell above and the cell to the left.

4fill in blank

hard

Fill both blanks to complete the function signature and return statement.

DSA Rust

fn unique_paths([1]: usize, [2]: usize) -> usize {
    // function body
    dp[m - 1][n - 1]
}

Drag options to blanks, or click blank then click option'

Am

Bn

Cusize

Di32

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong parameter names

Using incorrect types like i32 instead of usize

The function takes two parameters: m and n, both of type usize representing grid dimensions.

5fill in blank

hard

Fill all three blanks to complete the DP initialization and loop ranges.

DSA Rust

let mut dp = vec![vec![0usize; [1]]; [2]];
for i in 0..[3] {
    dp[i][0] = 1usize;
}

Drag options to blanks, or click blank then click option'

Am

Bn

Cm - 1

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping m and n

Using m - 1 or n - 1 incorrectly in loop range

The DP table has m rows and n columns. The loop runs from 0 to m to set the first column paths.

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