Unique Paths in Grid DP in DSA Rust - Execution Trace

Concept Flow - Unique Paths in Grid DP

Start at top-left cell (0,0)

↓

Initialize DP table with 1s in first row and first column

↓

For each cell (i,j) from (1,1) to (m-1,n-1)

↓

Calculate dp[i

↓

Repeat until bottom-right cell (m-1,n-1)

↓

Return dp[m-1

We fill a table where each cell counts paths from start by adding paths from top and left cells.

Execution Sample

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]
}

Calculates number of unique paths in an m x n grid moving only right or down.

Execution Table

Step	Operation	Cell Updated	Value Computed	DP Table State
0	Initialize dp with 1s	All cells in first row and column	1	[[1,1,1],[1,1,1],[1,1,1]]
1	Calculate dp[1][1]	(1,1)	dp[0][1] + dp[1][0] = 1 + 1 = 2	[[1,1,1],[1,2,1],[1,1,1]]
2	Calculate dp[1][2]	(1,2)	dp[0][2] + dp[1][1] = 1 + 2 = 3	[[1,1,1],[1,2,3],[1,1,1]]
3	Calculate dp[2][1]	(2,1)	dp[1][1] + dp[2][0] = 2 + 1 = 3	[[1,1,1],[1,2,3],[1,3,1]]
4	Calculate dp[2][2]	(2,2)	dp[1][2] + dp[2][1] = 3 + 3 = 6	[[1,1,1],[1,2,3],[1,3,6]]
5	Return result	(2,2)	6	[[1,1,1],[1,2,3],[1,3,6]]

💡 Reached bottom-right cell (2,2), dp[2][2] = 6 is total unique paths

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
dp	[[1,1,1],[1,1,1],[1,1,1]]	[[1,1,1],[1,2,1],[1,1,1]]	[[1,1,1],[1,2,3],[1,1,1]]	[[1,1,1],[1,2,3],[1,3,1]]	[[1,1,1],[1,2,3],[1,3,6]]	[[1,1,1],[1,2,3],[1,3,6]]

Key Moments - 3 Insights

Why do we initialize the first row and first column with 1s?

Because from the start cell, there is only one way to reach any cell in the first row (all moves right) or first column (all moves down). This is shown in execution_table step 0.

Why do we add dp[i-1][j] and dp[i][j-1] to get dp[i][j]?

Because to reach cell (i,j), you can come either from the cell above (i-1,j) or from the cell to the left (i,j-1). So total paths are sum of those two, as shown in steps 1 to 4.

Why does the loop start from 1 instead of 0?

Because the first row and column are already initialized with 1s, so we start filling from cell (1,1) to avoid overwriting those base cases, as seen in the code and execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of dp[1][2] after step 2?

A 3

B 2

C 1

D 6

💡 Hint

Check the 'Value Computed' and 'DP Table State' columns in row with Step 2.

At which step does the dp table first show a value greater than 3?

A Step 1

B Step 4

C Step 2

D Step 3

💡 Hint

Look at the 'Value Computed' column and DP table states for values > 3.

If the grid size was 2x2, how many steps would the inner loops run to fill dp?

A 2

B 3

C 1

D 4

💡 Hint

For a 2x2 grid, loops start at 1 and go to m-1 and n-1, so only one cell (1,1) is updated.

Concept Snapshot

Unique Paths DP:
- Use a 2D dp array of size m x n
- Initialize first row and column with 1
- For each cell dp[i][j], dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Result is dp[m-1][n-1]
- Counts paths moving only right or down

Full Transcript

This concept shows how to count unique paths in a grid using dynamic programming. We create a table dp where each cell stores the number of ways to reach it from the start. We initialize the first row and column with 1 because there is only one way to reach those cells by moving right or down only. Then for each other cell, we add the number of ways to reach the cell above and the cell to the left. This way, we build up the total paths step by step until we reach the bottom-right cell. The final answer is the value in dp[m-1][n-1]. The execution table shows each update to the dp table and how values accumulate. This method efficiently counts all unique paths without enumerating them.

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