Unique Paths in Grid DP in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP array with the number of rows.

DSA C#

int m = grid.GetLength(0);
int n = grid.GetLength(1);
int[,] dp = new int[[1], n];

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

A1

Bm

Cm + n

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of m for the number of rows.

Confusing rows and columns in array dimensions.

The number of rows is stored in variable m, so dp array should have m rows.

2fill in blank

medium

Complete the code to set the base case for the first row in the DP array.

DSA C#

for (int j = 0; j < n; j++) {
    if (grid[0, j] == 1) break;
    dp[0, j] = [1];
}

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

A1

Bj

C0

Dgrid[0, j]

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[0, j] to 0 instead of 1.

Using grid value directly instead of 1.

The first row cells before any obstacle have exactly 1 unique path to reach.

3fill in blank

hard

Fix the error in the nested loop that fills the DP array for unique paths.

DSA C#

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        if (grid[i, j] == 1) {
            dp[i, j] = 0;
        } else {
            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.

Forgetting to handle obstacles by setting dp[i, j] to 0.

The number of unique paths to a cell is the sum of paths from the top and left cells.

4fill in blank

hard

Fill both blanks to initialize the first column and first row of the DP array correctly.

DSA C#

for (int i = 0; i < m; i++) {
    if (grid[i, 0] == 1) break;
    dp[i, 0] = [1];
}
for (int j = 0; j < n; j++) {
    if (grid[0, j] == 1) break;
    dp[0, j] = [2];
}

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

A1

B0

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 for initialization.

Using loop variables i or j as values.

Both first column and first row cells before obstacles have 1 unique path.

5fill in blank

hard

Fill all three blanks to complete the method that returns the number of unique paths avoiding obstacles.

DSA C#

public int UniquePathsWithObstacles(int[,] grid) {
    int m = grid.GetLength(0);
    int n = grid.GetLength(1);
    int[,] dp = new int[m, n];

    for (int i = 0; i < m; i++) {
        if (grid[i, 0] == 1) break;
        dp[i, 0] = [1];
    }
    for (int j = 0; j < n; j++) {
        if (grid[0, j] == 1) break;
        dp[0, j] = [2];
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (grid[i, j] == 1) {
                dp[i, j] = 0;
            } else {
                dp[i, j] = dp[i - 1, j] [3] dp[i, j - 1];
            }
        }
    }

    return dp[m - 1, n - 1];
}

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

A1

B0

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 for initialization.

Using subtraction instead of addition for combining paths.

Initialize first row and column with 1 until obstacles, then sum paths from top and left cells.

Practice

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

easy

A. The maximum sum path from the top-left to the bottom-right corner of a grid.

B. The shortest path length from the top-left to the bottom-right corner of a grid.

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

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 to bottom-right corner moving only right or down.

2. Step 2: Differentiate from other path problems

   It is not about shortest path or sums, but counting unique ways to reach the destination.

3. Final Answer:

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

4. Quick Check:

   Unique paths count = number of ways [OK]

Hint: Count paths by moving only right or down [OK]

Common Mistakes:

• Confusing unique paths with shortest path length
• Including diagonal moves
• Counting obstacles instead of paths

2. Which of the following C# code snippets correctly initializes a 2D array for dynamic programming of size m x n?

easy

A. int[,] dp = new int[m, n];

B. int[][] dp = new int[m][n];

C. int[][] dp = new int[m, n];

D. int[,] dp = new int[m][];

Solution

1. Step 1: Recall C# 2D array syntax

   In C#, a rectangular 2D array is declared as int[,] dp = new int[m, n];

2. Step 2: Identify incorrect syntax

   Options B, C, and D misuse jagged array or rectangular array syntax.

3. Final Answer:

   int[,] dp = new int[m, n]; -> Option A

4. Quick Check:

   Rectangular 2D array uses [,] syntax [OK]

Hint: Use int[,] for 2D arrays, not jagged syntax [OK]

Common Mistakes:

• Using jagged array syntax incorrectly
• Mixing rectangular and jagged array declarations
• Missing array size initialization

3. What is the output of the following C# code snippet for Unique Paths in a 3x3 grid?

int m = 3, n = 3;
int[,] dp = new int[m, n];
for (int i = 0; i < m; i++) dp[i, 0] = 1;
for (int j = 0; j < n; j++) dp[0, j] = 1;
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
    }
}
Console.WriteLine(dp[m - 1, n - 1]);

medium

A. 10

B. 3

C. 9

D. 6

Solution

1. Step 1: Initialize first row and column

   First row and column are set to 1, representing only one path along edges.

2. Step 2: Calculate dp values for inner cells

   Each cell dp[i,j] = dp[i-1,j] + dp[i,j-1]. For 3x3 grid, dp[2,2] = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Use dp[i,j] = dp[i-1,j] + dp[i,j-1] to fill grid [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Adding instead of summing paths
• Off-by-one errors in loops

4. Identify the error in the following C# code snippet for Unique Paths calculation:

int m = 3, n = 3;
int[,] dp = new int[m, n];
for (int i = 0; i <= m; i++) dp[i, 0] = 1;
for (int j = 0; j <= n; j++) dp[0, j] = 1;
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
    }
}
Console.WriteLine(dp[m - 1, n - 1]);

medium

A. The dp array is not initialized.

B. The loops use <= causing index out of range exception.

C. The dp formula is incorrect; it should subtract values.

D. The Console.WriteLine statement is missing a semicolon.

Solution

1. Step 1: Check loop boundaries

   Loops use i <= m and j <= n which exceed array bounds (max index m-1, n-1).

2. Step 2: Identify runtime error

   This causes IndexOutOfRangeException at runtime when accessing dp[m,0] or dp[0,n].

3. Final Answer:

   The loops use <= causing index out of range exception. -> Option B

4. Quick Check:

   Loop bounds must be less than array size [OK]

Hint: Use < not <= for array indices to avoid out of range [OK]

Common Mistakes:

• Using <= instead of < in loops
• Ignoring array index limits
• Misunderstanding zero-based indexing

5. Given a 4x5 grid with some obstacles represented by 1s, how would you modify the Unique Paths DP solution to count paths avoiding obstacles?

int[,] obstacleGrid = {
  {0,0,0,0,0},
  {0,1,0,1,0},
  {0,0,0,0,0},
  {1,0,1,0,0}
};

Which approach correctly adapts the DP solution?

hard

A. Initialize dp[i,j] = 0 if obstacleGrid[i,j] == 1; else dp[i,j] = dp[i-1,j] + dp[i,j-1] (with boundary checks). Initialize first row and column carefully considering obstacles.

B. Ignore obstacles and calculate dp as usual because obstacles don't affect path count.

C. Set dp[i,j] = 1 for all cells and subtract 1 for obstacles at the end.

D. Use recursion without memoization to handle obstacles.

Solution

1. Step 1: Set dp to 0 where obstacles exist

   For cells with obstacleGrid[i,j] == 1, dp[i,j] must be 0 to block paths.

2. Step 2: Calculate dp with obstacle checks

   For other cells, dp[i,j] = dp[i-1,j] + dp[i,j-1], ensuring no paths through obstacles. Initialize first row and column carefully to stop paths after obstacles.

3. Final Answer:

   Initialize dp[i,j] = 0 if obstacleGrid[i,j] == 1; else dp[i,j] = dp[i-1,j] + dp[i,j-1] (with boundary checks). Initialize first row and column carefully considering obstacles. -> Option A

4. Quick Check:

   Obstacles block paths, set dp=0 there [OK]

Hint: Set dp=0 on obstacles, sum neighbors otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Not initializing first row/column correctly with obstacles
• Using recursion without memoization causing inefficiency