Unique Paths in Grid DP in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unique Paths Calculation

What is the output of the following C# code that calculates unique paths in a 3x3 grid?

DSA C#

int UniquePaths(int m, int n) {
    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];
        }
    }
    return dp[m - 1, n - 1];
}

Console.WriteLine(UniquePaths(3, 3));

A 3

B 6

C 9

D 12

💡 Hint

Think about how many ways you can move right or down to reach the bottom-right corner.

The number of unique paths in a 3x3 grid is 6 because you can only move right or down, and the total moves are fixed. The DP table sums paths from top and left cells.

🧠 Conceptual

intermediate

Understanding DP Table Initialization

Why do we initialize the first row and first column of the DP table with 1s in the Unique Paths problem?

A Because the first row and column are always zero in the DP table.

B Because the first row and column represent obstacles that block paths.

C Because there is only one way to reach any cell in the first row or column by moving only right or down.

D Because the first row and column represent the maximum number of paths possible.

💡 Hint

Think about how you can move from the start to cells in the first row or column.

The first row and column can only be reached by moving straight right or straight down respectively, so there is exactly one path to each of those cells.

❓ Predict Output

advanced

Output with Obstacle Grid

What is the output of the following C# code that calculates unique paths in a 3x3 grid with an obstacle at position (1,1)?

DSA C#

int UniquePathsWithObstacles(int[,] obstacleGrid) {
    int m = obstacleGrid.GetLength(0);
    int n = obstacleGrid.GetLength(1);
    int[,] dp = new int[m, n];
    if (obstacleGrid[0, 0] == 1) return 0;
    dp[0, 0] = 1;
    for (int i = 1; i < m; i++) {
        dp[i, 0] = (obstacleGrid[i, 0] == 0 && dp[i - 1, 0] == 1) ? 1 : 0;
    }
    for (int j = 1; j < n; j++) {
        dp[0, j] = (obstacleGrid[0, j] == 0 && dp[0, j - 1] == 1) ? 1 : 0;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i, j] == 0) {
                dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
            } else {
                dp[i, j] = 0;
            }
        }
    }
    return dp[m - 1, n - 1];
}

int[,] grid = new int[,] {
    {0, 0, 0},
    {0, 1, 0},
    {0, 0, 0}
};
Console.WriteLine(UniquePathsWithObstacles(grid));

A 2

B 4

C 3

D 5

💡 Hint

The obstacle blocks some paths, reducing the total count.

The obstacle at (1,1) blocks paths passing through that cell. The DP table counts only paths avoiding obstacles, resulting in 2 unique paths.

🔧 Debug

advanced

Identify the Bug in DP Implementation

What error will this code produce when calculating unique paths for a 3x3 grid?

DSA C#

int UniquePaths(int m, int n) {
    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];
        }
    }
    return dp[m - 1, n - 1];
}

Console.WriteLine(UniquePaths(3, 3));

A IndexOutOfRangeException

B Returns 6

C NullReferenceException

D Compilation error

💡 Hint

Check the loop conditions for array indexing.

The loops use <= which causes index to go out of bounds since arrays are zero-indexed and length is m or n.

🚀 Application

expert

Number of Unique Paths in a 5x5 Grid with Obstacles

Given the following 5x5 grid with obstacles (1 represents an obstacle, 0 is free), what is the number of unique paths from top-left to bottom-right moving only right or down?

DSA C#

int[,] grid = new int[,] {
    {0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {1, 0, 1, 0, 0},
    {0, 0, 0, 1, 0}
};

int UniquePathsWithObstacles(int[,] obstacleGrid) {
    int m = obstacleGrid.GetLength(0);
    int n = obstacleGrid.GetLength(1);
    int[,] dp = new int[m, n];
    if (obstacleGrid[0, 0] == 1) return 0;
    dp[0, 0] = 1;
    for (int i = 1; i < m; i++) {
        dp[i, 0] = (obstacleGrid[i, 0] == 0 && dp[i - 1, 0] == 1) ? 1 : 0;
    }
    for (int j = 1; j < n; j++) {
        dp[0, j] = (obstacleGrid[0, j] == 0 && dp[0, j - 1] == 1) ? 1 : 0;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i, j] == 0) {
                dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
            } else {
                dp[i, j] = 0;
            }
        }
    }
    return dp[m - 1, n - 1];
}

Console.WriteLine(UniquePathsWithObstacles(grid));

A 9

B 5

C 4

D 7

💡 Hint

Carefully count paths avoiding obstacles using the DP approach.

The DP table counts paths avoiding obstacles. After filling, the bottom-right cell shows 7 unique paths.

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